1806: 睡美人

    王子终于来到了熟睡的公主的身边了，只需要亲吻公主就可以成功唤醒公主。但是邪恶的巫婆在公主身上盖了很多魔毯，魔毯有红蓝两种颜色王子需要移除所有的魔毯才能亲吻公主，现在王子手里有三瓶魔法药水（都必须使用且只能使用一次），1号药水可以随机改变原来魔毯的覆盖顺序（有可能不发生改变），2号药水可以合并所有相邻且颜色相同的魔毯为一条魔毯，3号药水可以恰好（大于或小于m都无法移除）移除m个魔毯，药水需要按照编号为1、2、3的顺序使用。用0表示红色魔毯1表示蓝色魔毯，例如一开始魔毯顺序为"0101"、m=3，经过1号药水随机变换后顺序可能为"1001"，使用2号药水后序列变为"101"，最后使用3号药水恰好可以移除所有魔毯，这称之为一种移除成功的可能反之称之为一种移除失败的可能。     现在王子想知道移除成功和移除失败的可能数分别为多少，结果可能很大需要对1e9+7取模。

   第一行两个正整数n、m分表示魔毯的数量和3号药水恰好移除的魔毯数。

   第二行个只包含0和1的字符串s。

（输入保证红色魔毯和蓝色魔毯都至少存在一条）

（2<=n<=1e6， 1<=m<=1e9）

两个非负整数，分别表示移除成功和移除失败的可能数。

4 2
1010

2 4