[JSOI2016]位运算

题目描述

JYY 最近在研究位运算。他发现位运算中最有趣的就是异或 (xor) 运算。对于两个数的异或运算,JYY 发现了一个结论:两个数的异或值为 $0$ 当且仅当他们相等。于是 JYY 又开始思考,对于 $N$ 个数的异或值会有什么性质呢? JYY 想知道,如果在 $0$ 到 $R-1$ 的范围内,选出 $N$ 个不同的整数,并使得这 $N$ 个整数的异或值为 $0$,那么一共有多少种选择的方法呢?(选择的不同次序并不作重复统计,请参见样例) JYY 是一个计算机科学家,所以他脑海里的 $R$ 非常非常大。为了能够方便的表达,如果我们将 $R$ 写成一个 $01$ 串,那么 $R$ 是由一个较短的 $01$ 串 $S$ 重复 $K$ 次得到的。比如,若 $S=101$,$K=2$,那么 $R$ 的二进制表示则为 $101101$。由于计算的结果会非常大,JYY 只需要你告诉他选择的总数对 $10^9+7$ 取模的结果即可。

输入输出格式

输入格式


第一行包含两个正整数 $N$ 和 $K$; 接下来一行包含一个由 $0$ 和 $1$ 组成的字符串 $S$; 我们保证 $S$ 的第一个字符一定为 $1$。

输出格式


一行一个整数,表示选择的方案数对 $10^9+7$ 取模的值。

输入输出样例

输入样例 #1

3 1
100

输出样例 #1

1

说明

**样例说明** 唯一的一种选择方法是选择 $\{1,2,3\}$。 ------ **数据范围** 对于 $100\%$ 的数据,$3 \le N \le 7$,$1 \le k \le 10^5$,$1 \le |S| \le 50$。