#P5772. [JSOI2016] 位运算

[JSOI2016] 位运算

题目描述

JYY 最近在研究位运算。他发现位运算中最有趣的就是异或 (xor) 运算。对于两个数的异或运算,JYY 发现了一个结论:两个数的异或值为 00 当且仅当他们相等。于是 JYY 又开始思考,对于 NN 个数的异或值会有什么性质呢?

JYY 想知道,如果在 00R1R-1 的范围内,选出 NN 个不同的整数,并使得这 NN 个整数的异或值为 00,那么一共有多少种选择的方法呢?(选择的不同次序并不作重复统计,请参见样例)

JYY 是一个计算机科学家,所以他脑海里的 RR 非常非常大。为了能够方便的表达,如果我们将 RR 写成一个 0101 串,那么 RR 是由一个较短的 0101SS 重复 KK 次得到的。比如,若 S=101S=101K=2K=2,那么 RR 的二进制表示则为 101101101101。由于计算的结果会非常大,JYY 只需要你告诉他选择的总数对 109+710^9+7 取模的结果即可。

输入格式

第一行包含两个正整数 NNKK

接下来一行包含一个由 0011 组成的字符串 SS

我们保证 SS 的第一个字符一定为 11

输出格式

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

3 1
100
1

提示

样例说明

唯一的一种选择方法是选择 {1,2,3}\{1,2,3\}


数据范围

对于 100%100\% 的数据,3N73 \le N \le 71k1051 \le k \le 10^51S501 \le |S| \le 50