众所周知，以下字符串 $s(n) = s_0s_1 \dots s_{2^n-1}$ 可以挑战几乎所有使用模 $2^{64}$ 多项式哈希的解法：

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

其中 $\text{popcount}(i)$ 表示数字 $i$ 二进制表示中 $1$ 的个数。

给定一个字符串 $u$ 和一个整数 $n$，求 $u$ 在字符串 $s(n)$ 中出现的次数，以及在 $s(n)$ 中出现次数与 $u$ 相同的不同字符串 $v$ 的个数。由于这两个数字可能非常大，你只需要计算它们对 $10^9 + 7$ 取模后的结果。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^{18}$)。

第二行包含一个字符串 $u$ ($1 \le |u| \le \min(10^6, 2^n)$)，仅由字母 "a" 和 "b" 组成。

保证所有测试数据中 $|u|$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，如果字符串 $u$ 没有在 $s(n)$ 中出现，直接输出 $-1$。否则，输出两个整数，分别表示 $u$ 在 $s(n)$ 中出现的次数对 $10^9 + 7$ 取模的结果，以及在 $s(n)$ 中出现次数与 $u$ 相同的不同字符串 $v$ 的个数对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

4
10
a
10
abba
5
abbabaabbaababbabaababbaabbabaab
20
ababab

样例输出 1

512 2
171 4
1 344
-1