最小操作次数

题目描述

有一个仅由 0、1、? 组成的字符串 $S$。把该字符串首尾相连 $K$ 次得到的字符串记为 $T$。

把该字符串中所有的 ? 都替换成 0 或 1，设 $S$ 中包含的 ? 的个数为 $q$，则这样的替换共有 $2^{Kq}$ 种。请对其中所有的替换结果解答以下问题，并输出答案之和除以 $(10^9+7)$ 的余数。

把替换 ? 后得到的字符串记为 $T'$。对 $T'$ 反复执行以下操作，要把所有字符变成相同时，所需的最小操作次数是多少次？

• 选择满足 $1 \le l \le r \le |T'|$ 的整数 $l, r$。然后把 $T'$ 的第 $l$ 个字符到第 $r$ 个字符（含两端）中的每个字符，0 改成 1、1 改成 0。

输入格式

输入按以下格式从标准输入给出：

$S$
$K$

输出格式

以整数形式输出答案。

样例

101
2

2

字符串 $T=$ 101101，其中不包含 ?。因此，只需要求出唯一的 $T'=$ 101101 的答案即可。

例如，按 101101 $\rightarrow$ 110011 $\rightarrow$ 111111 操作，可以用 $2$ 次把所有字符变成相同。

不可能用 $1$ 次以内的操作把所有字符变成相同。

?0?
1

3

可能的字符串 $T'$ 有 000, 001, 100, 101 这 $4$ 种。

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

235562598

答案有时会非常大，请输出除以 $(10^9+7)$ 的余数。

数据范围

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