给你一个长度为 的字符串 ，仅由 0、1、? 三种字符组成。
0
1
?
给你 组询问形如 ，满足 且 0，1，? 。
对于第 个询问，你要做出如下操作：
注：子序列是指由原串中任意个不一定连续，但保持原有先后顺序的字符构成的字符串。
行，第 行为满足条件的字符串数量 。
样例输入 1
3 3 100 2 1 2 ? 3 ?
样例输出 1
5 7 10
样例解释 1
110
10
11
1?0
100
00
1??
101
111
01
样例输入 2
40 10 011?0??001??10?0??0?0?1?11?1?00?11??0?01 5 0 2 ? 30 ? 7 1 11 1 3 1 25 1 40 0 12 1 18 1
样例输出 2
746884092 532460539 299568633 541985786 217532539 217532539 217532539 573323772 483176957 236273405