题目描述

猫 Taro 和兔子 Hanako 发明了一种新的“生命游戏”。

有 $N$ 个格子按圆环排列，编号为 $0,1,\ldots,N-1$。对于 $0\le i<N-1$，格子 $i$ 与格子 $i+1$ 相邻；格子 $N-1$ 与格子 $0$ 也相邻。因此，每个格子恰好有两个相邻格子。

每个格子有两种状态：存活（1）或 死亡（0）。

在时刻 $0$，Taro 和 Hanako 可以决定所有尚未确定的格子的状态。对于任意时刻 $t>0$，所有格子的状态根据时刻 $t-1$ 的状态同时更新：

• 对于格子 $i$，考虑它自身以及与它相邻的两个格子，共三个格子；
• 如果这三个格子中至少有两个在时刻 $t-1$ 处于存活状态，那么格子 $i$ 在时刻 $t$ 处于存活状态；
• 否则，这三个格子中至少有两个处于死亡状态，格子 $i$ 在时刻 $t$ 处于死亡状态。

给定一个字符串 init。令 $N=|\texttt{init}|$。其中：

• init[i] = '1' 表示格子 $i$ 在时刻 $0$ 已确定为存活；
• init[i] = '0' 表示格子 $i$ 在时刻 $0$ 已确定为死亡；
• init[i] = '?' 表示格子 $i$ 在时刻 $0$ 的状态尚未确定，可以选择为 0 或 1。

你需要统计有多少种给所有 ? 赋值的方法，使得经过恰好 $T$ 次更新后，至少有 $K$ 个格子处于存活状态。

输入格式

第一行输入一个字符串 init。

第二行输入两个整数 $T,K$。

输出格式

输出一个整数，表示满足条件的初始状态赋值方案数。

输入输出样例 #1

输入 #1

0?1
1 1

输出 #1

1

输入输出样例 #2

输入 #2

?????????
0 1

输出 #2

511

输入输出样例 #3

输入 #3

??0???????
58 6

输出 #3

151

输入输出样例 #4

输入 #4

?????????1
47 3

输出 #4

453

输入输出样例 #5

输入 #5

??01??110?
100 3

输出 #5

29

输入输出样例 #6

输入 #6

??????????????????????????????????????????????????
1000 0

输出 #6

1125899906842624

输入输出样例 #7

输入 #7

010101
10 4

输出 #7

0

输入输出样例 #8

输入 #8

10101
2 5

输出 #8

1

样例说明

对于样例 #1，唯一的 ? 可以填成 0 或 1：

• 初始状态为 001 时，经过一次更新后变为 000，没有存活格子；
• 初始状态为 011 时，经过一次更新后变为 111，共有 $3$ 个存活格子。

因此只有后一种赋值满足至少有 $1$ 个格子存活，答案为 $1$。

对于样例 #2，由于 $T=0$，不进行任何更新。共有 $2^9=512$ 种赋值，其中只有全为 0 的状态不满足至少有一个存活格子的要求，因此答案为 $511$。

数据范围与约定

• $3\le |\texttt{init}|\le 50$；
• init 中每个字符均为 0、1 或 ?；
• $0\le T\le 1000$；
• $0\le K\le |\texttt{init}|$。