#8322. 「JXOI Test Round 1」一道助 AK 好题 提高+/省选−

“Kotomija，你会下棋吗？”

“？”

个士兵棋子排成一行，每个士兵要么是 Kotomija 的要么是 Kim-Jong 的。接下来有若干天，每天如果第 个士兵和第 只士兵不属于同一玩家，那么第 只士兵会击杀第 只士兵。所有击杀操作会同时进行，士兵被击杀后会被移除。例如，如果某一天第 3 个士兵击杀第 4 个士兵，第 4 个士兵击杀第 5 个士兵，那么结果就是第 4 个和第 5 个士兵都会被移除。

现在 Kotomija 和 Kim-Jong 已经在一些位置上摆好自己的士兵了，但他们还没确认其余位置摆什么士兵。你需要对于所有方案，求出 天后剩下的士兵数的总和，答案对 取模。

第一行输入两个正整数 。

第二行包含一个字符串 。 表示第 个位置上摆了 Kotomija 的士兵， 表示第 个位置摆了 Kim-Jong 的士兵， 表示第 个位置还没摆士兵。

共一行，用一个正整数表示答案。

样例输入

5 1
01?10

样例输出

4

对于所有数据，保证 。