题目描述

考虑一个以压缩格式表示的非常大的数 $R$。压缩格式是一个二进制字符串 $s$ 和一个整数 $k$。从空字符串开始，将 $s$ 重复追加 $k$ 次，即可得到 $R$ 的二进制表示。字符串 $s$ 保证以 $1$ 开头。现在，对于这个 $R$，解决以下问题：有多少个由 $n$ 个互不相同的整数组成的集合，使得每个整数都在 $0$ 到 $R-1$ 之间（包含两端），并且所有这些整数的异或（XOR）等于零？由于这个数字可能非常大，请输出它对 $10^9 + 7$ 取模的结果。

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

$$\begin{aligned} 0 \oplus 0 &= 0 \\ 0 \oplus 1 &= 1 \\ 1 \oplus 0 &= 1 \\ 1 \oplus 1 &= 0 \\ \end{aligned}$$

XOR 满足结合律，因此 $a \oplus (b \oplus c) = (a \oplus b) \oplus c$。

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。每个输入由恰好两行组成。第一行包含两个空格分隔的整数 $n$（$3 \leq n \leq 7$）和 $k$（$1 \leq k \leq 100000$），其中 $n$ 是集合中互不相同整数的个数，$k$ 是为了构造 $R$ 而重复字符串 $s$ 的次数。第二行仅包含字符串 $s$，其长度至少为 $1$，至多为 $50$，每个字符是 $0$ 或 $1$。保证 $s$ 以 $1$ 开头。

输出格式

输出一行一个整数，表示可以形成的、由 $n$ 个互不相同整数组成的集合的数量，其中每个整数都在 $0$ 到 $R-1$ 之间（包含两端），并且每个集合中 $n$ 个整数的异或值为 $0$。输出该数字对 $10^9 + 7$ 取模的结果。

3 1
100

1

4 3
10

1978

5 100
1

598192244

提示

翻译由 DeepSeek V3.2 完成