{"problem":{"name":"Minflip Summation","description":{"content":"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 th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc200_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $1 \\le |S| \\le 10^5$\n*   $1 \\le K \\le 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$S$\n$K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc200_f","tags":[],"sample_group":[["101\n2","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."],["?0?\n1","3\n\nWe have four candidates for $T'$: `000`, `001`, `100`, and `101`."],["10111?10??1101??1?00?1?01??00010?0?1??\n998244353","235562598\n\nSince the answer can be enormous, find it modulo $(10^9+7)$."]],"created_at":"2026-03-03 11:01:14"}}