6706: ABC200 —— F - Minflip Summation
[Creator : ]
Description
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$).
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.
Input
Input is given from Standard Input in the following format:
$S$
$K$
$S$
$K$
Output
Print the answer as an integer.
Constraints
$1≤∣S∣≤10^5$
$1 \le K \le 10^9$
$1 \le K \le 10^9$
Sample 1 Input
101
2
Sample 1 Output
2
We have T=$101$, which does not contain ?, so we just need to solve the problem for the only $T'=101$.
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.
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 2 Input
?0?
1
Sample 2 Output
3
We have four candidates for T′: 000, 001, 100, and 101.
Sample 3 Input
10111?10??1101??1?00?1?01??00010?0?1??
998244353
Sample 3 Output
235562598