Score : $600$ points

问题描述

我们有一个由 0、1 和 ? 组成的字符串 $S$。令 $T$ 为将 $S$ 连接 $K$ 次得到的字符串。 通过将 $T$ 中的每个 ? 替换为 0 或 1，我们可以得到 $2^{Kq}$ 个不同的字符串，其中 $q$ 是 $S$ 中 ? 的数量。针对这些字符串中的每一个解决以下问题，并求出所有答案之和，结果对 $(10^9+7)$ 取模。

让 $T'$ 表示通过替换 $T$ 中的 ? 得到的字符串。我们将重复执行以下操作以使 $T$ 中的所有字符变得相同。至少需要多少次操作才能实现这一点？

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

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have a string $S$ consisting of 0, 1, and ?. Let $T$ be the concatenation of $K$ copies of $S$.
By replacing each ? in $T$ with 0 or 1, we can obtain $2^{Kq}$ strings, where $q$ is the number of ?s in $S$. Solve the problem below for each of these strings and find the sum of all the answers, modulo $(10^9+7)$.

Let $T'$ be the string obtained by replacing ? in $T$. We will repeatedly do the operation below to make all the characters in $T$ the same. At least how many operations are needed for this?

• Choose integers $l$ and $r$ such that $1 \le l \le r \le |T'|$, and invert the $l$-th through $r$-th characters of $T$: from 0 and 1 and vice versa.

Constraints

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

Input

Input is given from Standard Input in the following format:

$S$

$K$

Output

Print the answer as an integer.

Sample Input 1

101
2

Sample Output 1

2

We have $T=$ 101101, which does not contain ?, so we just need to solve the problem for the only $T'=$ 101101.
We can make all the characters the same in two operations as, for example, 101101 $\rightarrow$ 110011 $\rightarrow$ 111111.
We cannot make all the characters the same in one or fewer operations.

Sample Input 2

?0?
1

Sample Output 2

3

We have four candidates for $T'$: 000, 001, 100, and 101.

Sample Input 3

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

Sample Output 3

235562598

Since the answer can be enormous, find it modulo $(10^9+7)$.

update @ 2024/3/10 09:12:29