分数: 600 点
问题陈述
我们有一个字符串 S 组成 0, 1,和 ?。让 T 是以下的串联 K 副本 S.
通过替换每个 ? in T 与 0 or 1,我们可以得到 2^{Kq} 字符串,其中 q 是数量 ?位于 S。针对每个字符串解决以下问题,并求出所有答案的总和(取模) (10^9+7).
让 T' 为替换后得到的字符串
?in T。我们将重复执行下面的操作,使所有字符都出现在 T 相同。这至少需要多少次操作?
- 选择整数 l 和 r 这样 1 \le l \le r \le |T'|,并反转 l-th 通过 r第一个字符 T:来自
0和1反之亦然。
约束
- 1 \le |S| \le 10^5
- 1 \le K \le 10^9
输入
输入由标准输入按以下格式给出:
S K
输出
将答案打印为整数。
示例输入 1
101 2
示例输出 1
2
我们有 T= 101101,其中不包含 ?,所以我们只需要解决唯一的问题 T'= 101101.
我们可以在两次操作中使所有字符相同,例如, 101101 \rightarrow 110011 \rightarrow 111111.
我们无法通过一次或更少的操作使所有字符都相同。
示例输入 2
?0? 1
示例输出 2
3
我们有四位候选人 T': 000, 001, 100,和 101.
示例输入 3
10111?10??1101??1?00?1?01??00010?0?1?? 998244353
示例输出 3
235562598
由于答案可能很大,请对它求模 (10^9+7).