F - Minflip Summation

得分：$600$ 分

问题描述

我们有一个由 0，1 和 ? 组成的字符串 $S$。令 $T$ 为 $K$ 个 $S$ 的拼接。
通过用 0 或者 1 替换 $T$ 中的每个 ?，我们可以得到 $2^{Kq}$ 个字符串，其中 $q$ 是 $S$ 中 ? 的个数。对于每个字符串，解决以下问题并求出所有答案的和，对 $(10^9+7)$ 取模。

令 $T'$ 为 $T$ 中所有 ? 被替换后的字符串。我们重复下面的操作使得 $T$ 所有字符相同。至少需要多少次操作？

• 选择整数 $l$ 和 $r$，使得 $1 \le l \le r \le |T'|$，然后反转 $T$ 的第 $l$ 到第 $r$ 个字符：将 0 和 1 互换。

约束

• $1 \le |S| \le 10^5$
• $1 \le K \le 10^9$

输入

输入从标准输入读取，具体格式如下：

$S$

$K$

输出

输出一个整数表示答案。

101
2

2

我们有 $T=$ 101101，其中不包含 ?，所以我们只需要针对唯一的 $T'=$ 101101 解决问题。
我们可以通过两次操作让所有字符相同，例如 101101 $\rightarrow$ 110011 $\rightarrow$ 111111。
我们无法通过一次或更少的操作让所有字符相同。

?0?
1

3

我们有四个候选的 $T'$： 000，001，100，101。

10111?10??1101??1?00?1?01??00010?0?1??
998244353

235562598

由于答案可能很大，对 $(10^9+7)$ 取模。