/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
0, 1, ? のみからなる文字列 S があります。この文字列を K 個連結したものを T とします。
この文字列の ? を全て 0 か 1 に置き換えた文字列は、S の中に含まれる ? の数を q 個とすると、全部で 2^{Kq} 通り考えられますが、その全てについて以下の問題を解いて、その答えの和を (10^9+7) で割った余りを求めてください。
?を置き換えた後の文字列を T' とします。T' に以下の操作を繰り返し行うことで全ての文字を同じにするとき、必要な最小の操作回数は何回ですか？
- 1 \le l \le r \le |T'| となる整数 l,r を選ぶ。そして、T' の l 文字目から r 文字目(両端含む)までの各文字を、
0であれば1に、1であれば0に変更する。
制約
- 1 \le |S| \le 10^5
- 1 \le K \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
S K
出力
答えを整数として出力せよ。
入力例 1
101 2
出力例 1
2
文字列 T= 101101 で、ここには ? が含まれません。よって、考えられる唯一の T'= 101101 についての答えを求めればよいです。
例えば、101101 \rightarrow 110011 \rightarrow 111111 と操作を行えば、 2 回で全ての文字列を同じにすることができます。
1 回以下の操作で全ての文字列を同じにすることはできません。
入力例 2
?0? 1
出力例 2
3
文字列 T' として考えられるものは 000, 001, 100, 101 の 4 通りです。
入力例 3
10111?10??1101??1?00?1?01??00010?0?1?? 998244353
出力例 3
235562598
答えは非常に大きくなることがあるので、 (10^9+7) で割った余りを求めてください。
Score : 600 points
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
0and1and 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.
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 \rightarrow 110011 \rightarrow 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 (10^9+7).