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$.
SampleInput
4
10
a
10
abba
5
abbabaabbaababbabaababbaabbabaab
20
ababab