Anti-hash Test

Problem Description

It is well known that the following string $s(n)=s_0s_1 \dots s_{2^n-1}$ can challenge almost every solution that uses polynomial hashes modulo $2^{64}$:

$$s_i=\begin{cases} a & \text{popcount(i)} \bmod 2 = 0 \\ b & \text{popcount(i)} \bmod 2 = 1 \end{cases} $$

where $\text{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 $10^9 + 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 $n$ ($1 \le n \le 10^{18}$). The second line contains a string $u$ ($1 \le |u| \le \min(10^6, 2^n)$) 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 $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 $10^9 + 7$ and the number of distinct strings $v$ which have the same number of occurrences in string $s(n)$ modulo $10^9 + 7$.

Sample Input

4
10
a
10
abba
5
abbabaabbaababbabaababbaabbabaab
20
ababab

Sample Output

512 2
171 4
1 344
-1

Source

2020 Multi-University Training Contest 10