{"raw_statement":[{"iden":"problem statement","content":"We have a string $S$ consisting of `0`, `1`, and `?`. Let $T$ be the concatenation of $K$ copies of $S$.  \nBy 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)$.\n\n> 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?\n> \n> *   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."},{"iden":"constraints","content":"*   $1 \\le |S| \\le 10^5$\n*   $1 \\le K \\le 10^9$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$S$\n$K$"},{"iden":"sample input 1","content":"101\n2"},{"iden":"sample output 1","content":"2\n\nWe have $T=$ `101101`, which does not contain `?`, so we just need to solve the problem for the only $T'=$ `101101`.  \nWe can make all the characters the same in two operations as, for example, `101101` $\\rightarrow$ `110011` $\\rightarrow$ `111111`.  \nWe cannot make all the characters the same in one or fewer operations."},{"iden":"sample input 2","content":"?0?\n1"},{"iden":"sample output 2","content":"3\n\nWe have four candidates for $T'$: `000`, `001`, `100`, and `101`."},{"iden":"sample input 3","content":"10111?10??1101??1?00?1?01??00010?0?1??\n998244353"},{"iden":"sample output 3","content":"235562598\n\nSince the answer can be enormous, find it modulo $(10^9+7)$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}