Anti-hash 테스트

다음 문자열 $s(n) = s_0 s_1 \ldots s_{2^n-1}$은 $2^{64}$를 법으로 하는 다항식 해시를 사용하는 거의 모든 풀이를 공격할 수 있다.

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

여기서 $\mathrm{popcount}(i)$는 $i$의 이진 표현에서 1의 개수이다.

문자열 $u$와 정수 $n$이 주어진다. $s(n)$에서 $u$가 나타나는 횟수와, $s(n)$에서 같은 횟수로 나타나는 서로 다른 문자열 $v$의 개수를 구하라. 두 값은 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구한다.

여러 개의 테스트 케이스가 주어진다. 첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다.

첫 줄에 정수 $n$ ($1 \le n \le 10^{18}$)이 주어진다.

둘째 줄에는 a와 b로만 이루어진 문자열 $u$ ($1 \le |u| \le \min(10^6, 2^n)$)가 주어진다.

모든 테스트 케이스의 $|u|$ 합은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 $u$가 $s(n)$에 나타나지 않으면 $-1$을 출력한다. 그렇지 않으면 $s(n)$에서 $u$의 출현 횟수를 $10^9 + 7$로 나눈 나머지와, $s(n)$에서 같은 출현 횟수를 갖는 서로 다른 문자열 $v$의 개수를 $10^9 + 7$로 나눈 나머지를 차례로 두 정수로 출력한다.