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

输入 #1

101
2

输出 #1

2

输入输出样例 #2

输入 #2

?0?
1

输出 #2

3

输入输出样例 #3

输入 #3

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

输出 #3

235562598

说明/提示

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