3948. 魔药

【题目描述】

王子终于来到了熟睡的公主的身边，只需要亲吻公主就可以成功唤醒公主。

但是邪恶的巫婆在公主身上盖了很多魔毯，魔毯有红蓝两种颜色王子需要移除所有的魔毯才能亲吻公主。

现在王子手里有三瓶魔法药水（都必须使用且只能使用一次），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

【样例说明】

样例说明：经过1号药水变换后s有6种可能{"1010","1001","1100","0011","0101","0110"}，其中"1100"和"0011"经过2号药水的变换后分别为"10"、"01"剩余魔毯数恰好2正好满足3号药水的使用条件。

【数据规模与约定】

38%的数据满足：n<=16

100%的数据满足：n<=1e6

【来源】

在此键入。