Problem 3501 --Anti-hash Test

3501: Anti-hash Test

$0.00\%$ 下一题

Time Limit	$1$ 秒/Second(s)	Memory Limit	$512$ 兆字节/Megabyte(s)
提交总数	$0$	正确数量	$0$
裁判形式	标准裁判/Standard Judge	我的状态	尚未尝试
难度		分类标签

Description

It is well known that the following string

s(n)=s0s1…s2n−1can challenge almost every solution that uses polynomial hashes modulo

264:

s i ={a b popcount(i)mod2=0 popcount(i)mod2=1

where

popcount(i)means the number of ones in binary representation of number

i.
Given a string

uand an integer

n, find the number of occurrences of

uin string

s(n)and the number of distinct strings

vwhich have the same number of occurrences in string

s(n). As both the numbers may be very large, you are only asked to calculate it modulo

109+7.

Input

There are multiple test cases. The first line of input contains an integer

T, indicating the number of test cases. For each test case:
The first line contains an integer

1≤n≤1018).
The second line contains a string

1≤|u|≤min(106,2n)) consisting only of letters `a' and `b'.
It is guaranteed that the size of the input file does not exceed 20M.6,2n)) consisting only of letters `a' and `b'.
It is guaranteed that the size of the input file does not exceed 20M.

Output

For each test cases, if the string

udoes not appear in string

s(n), you should simply output

−1. Otherwise, output two integers denoting the the number of occurrences of

uin string

s(n)modulo

109+7and the number of distinct strings

vwhich have the same number of occurrences in string

s(n)modulo

109+7.

Sample Input复制

4
10
a
10
abba
5
abbabaabbaababbabaababbaabbabaab
20
ababab

Sample Output复制

赛题来源/所属竞赛 2020 Multi-University Training Contest 10 N/A

竞赛编号	竞赛名称	竞赛时间	访问比赛

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[ms]
内存最少[KB]
第一AC
第一挑战