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 2Kq 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 (109+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≤l≤r≤∣T′∣, and invert the $l$-th through $r$-th characters of $T$: from 0 and 1 and vice versa.

Constraints

• 1≤∣S∣≤105
• 1≤K≤109

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 $\to$ 110011 $\to$ 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 (109+7).