Anti-hash Test

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

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

where $\mathrm{popcount}(i)$ is the number of ones in the binary representation of $i$.

Given a string $u$ and an integer $n$, find the number of occurrences of $u$ in $s(n)$ and the number of distinct strings $v$ that have the same number of occurrences in $s(n)$. Both numbers can be very large, so print them modulo $10^9 + 7$.

There are multiple test cases. The first line contains an integer $T$, the number of test cases. Each test case has two lines.

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 the letters a and b.

The sum of $|u|$ over all test cases does not exceed $10^6$.

For each test case, if $u$ does not appear in $s(n)$, print $-1$. Otherwise, print two integers: the number of occurrences of $u$ in $s(n)$ modulo $10^9 + 7$, and the number of distinct strings $v$ with the same number of occurrences in $s(n)$ modulo $10^9 + 7$.