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$。