It is well known that the following string s(n)=s0s1…s2n−1 can challenge almost every solution that uses polynomial hashes modulo 264:
si={abpopcount(i)mod2=0popcount(i)mod2=1
where popcount(i) means the number of ones in binary representation of number i.
Given a string u and an integer n, find the number of occurrences of u in string s(n) and the number of distinct strings v which 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.
输入格式
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 n (1≤n≤1018).
The second line contains a string u (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.
输出格式
For each test cases, if the string u does not appear in string s(n), you should simply output −1. Otherwise, output two integers denoting the the number of occurrences of u in string s(n) modulo 109+7 and the number of distinct strings v which have the same number of occurrences in string s(n) modulo 109+7.
输入样例
复制
4
10
a
10
abba
5
abbabaabbaababbabaababbaabbabaab
20
ababab