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.