题目描述

有一个寻找的东西，

星星在对我笑眯眯。

随着风儿眨着眼皮，

只要我伸出手就能抓到。

星之奏是一首成环传递，循环的童谣，连接过去与未来，它是希望之歌，却更是绝望之歌。 现在我们认为星之秦本源是长度为$\red{m}$的二进制串，由于星之秦的循环的，它还循环了$\red{k}$次，也就是现在的星之秦实际是长度为$\red{mk}$的二进制串，且拥有长度 为$\red{m}$的循环节。我们记星之奏二进制串表示的数字为$\red{R}$。

会唱星之奏的人恰好有$\red{R}$个，每个人唱星之奏有一个代表数字，哼唱的星之奏所能表示的数字是$\red{0 }$到$\red{R-1}$中的一个整数，不同的人对星之奏有不同的理解 ，因此不同人代表数字不一样。

现在选出一个大小为$\red{n}$的人的集合来合唱星之奏，我们希望这个这个集合的人的代表数字异或和为$\red{0，}$这样这$\red{n}$个人合唱的星之奏是优美的。 右多少个住合满足各件?答安对$\red{10^9+7}$取横。

输入格式

第一行两个整数分别表示$\red{n,k.}$

第二行一个字符串表示星之奏本源，长度为$\red{m}$。

输出格式

一行表示答案

样例

输入样例1

3 1

101

输出样例1

1

输入样例2

4 3

10

输出样例2

1978

输入样例3

5 100

1

输出样例3

598192244

提示

对于所有数据，保证满足$\red{m<=50000}$