考虑一个以压缩格式表示的巨大数字 $R$。它由一个二进制字符串 $s$ 和一个整数 $k$ 压缩而成。从空字符串开始，将 $s$ 重复拼接 $k$ 次，即可得到 $R$ 的二进制表示。保证字符串 $s$ 的首位为 $1$。现在，给定 $R$，请解决以下问题：有多少个包含 $n$ 个不同整数的集合，使得集合中每个整数都在 $0$ 到 $R-1$ 之间（包含 $0$ 和 $R-1$），且这 $n$ 个整数的异或和等于 $0$？由于这个数字可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

提醒一下，XOR 是异或运算。两个数字的异或运算是按位进行的。使用 $\oplus$ 表示异或：

$0 \oplus 0 = 0$ $0 \oplus 1 = 1$ $1 \oplus 0 = 1$ $1 \oplus 1 = 0$

异或满足结合律，即 $a \oplus (b \oplus c) = (a \oplus b) \oplus c$。

输入格式

每个输入包含一个测试用例。注意，你的程序可能会在不同的输入上运行多次。每个输入包含恰好两行。第一行包含两个空格分隔的整数 $n$ ($3 \le n \le 7$) 和 $k$ ($1 \le k \le 100\,000$)，其中 $n$ 是集合中不同整数的个数，$k$ 是为了构建 $R$ 而重复字符串 $s$ 的次数。第二行仅包含字符串 $s$，其长度至少为 $1$ 且最多为 $50$ 个字符，每个字符均为 $0$ 或 $1$。保证 $s$ 以 $1$ 开头。

输出格式

输出一行，包含一个整数，表示可以形成的包含 $n$ 个不同整数的集合数量，其中每个整数都在 $0$ 到 $R-1$ 之间，且集合中 $n$ 个整数的异或和为 $0$。将此结果对 $10^9 + 7$ 取模后输出。

样例

输入 1

3 1
100

输出 1

1

输入 2

4 3
10

输出 2

1978

输入 3

5 100
1

输出 3

598192244