AT_abc200_f [ABC200F] Minflip Summation

我们有一个字符串 $S$，由 `0`，`1` 和 `?` 组成，$T$ 为 $S$ 重复 $K$ 次的结果。 如果我们把 $T$ 中每个 `?` 都替换成 `0` 或 `1`，我们就能够得到 $2^{Kq}$ 种不同的字符串，其中 $q$ 是 $S$ 中 `?` 的数量。对于每个由如下规则生成的字符串，解决如下问题，把答案求和并模 $10^9+7$： > 设 $T'$ 为把 $T$ 中所有 `?` 替换为 `0` 或 `1` 得到的字符串。我们会重复执行如下操作，直到 $T$ 中所有元素均相同。最少需要多少次操作？ > > - 选择两个整数 $l,r$ 满足 $1 \le l \le r \le |T'|$，把 $S$ 的第 $l$ 个到第 $r$ 个字符取反。取反的意思是，`0` 变为 `1`，反之亦然。

输入格式如下： > $S$ > $K$

输出答案。

数据范围：$1 \le |S| \le 10^5$，$1 \le K \le 10^9$。