#abc200f. [abc200_f]Minflip Summation

[abc200_f]Minflip Summation

問題文

0, 1, ? のみからなる文字列 SS があります。この文字列を KK 個連結したものを TT とします。
この文字列の ? を全て 01 に置き換えた文字列は、SS の中に含まれる ? の数を qq 個とすると、全部で 2Kq2^{Kq} 通り考えられますが、その全てについて以下の問題を解いて、その答えの和を (109+7)(10^9+7) で割った余りを求めてください。

? を置き換えた後の文字列を TT' とします。TT' に以下の操作を繰り返し行うことで全ての文字を同じにするとき、必要な最小の操作回数は何回ですか?

  • 1lellerleT1 \\le l \\le r \\le |T'| となる整数 l,rl,r を選ぶ。そして、TT'll 文字目から rr 文字目(両端含む)までの各文字を、0 であれば 1 に、1 であれば 0 に変更する。

制約

  • 1leSle1051 \\le |S| \\le 10^5
  • 1leKle1091 \\le K \\le 10^9

入力

入力は以下の形式で標準入力から与えられる。

SS KK

出力

答えを整数として出力せよ。


入力例 1

101
2

出力例 1

文字列 T=T= 101101 で、ここには ? が含まれません。よって、考えられる唯一の T=T'= 101101 についての答えを求めればよいです。
例えば、101101 rightarrow\\rightarrow 110011 rightarrow\\rightarrow 111111 と操作を行えば、 22 回で全ての文字列を同じにすることができます。
11 回以下の操作で全ての文字列を同じにすることはできません。


入力例 2

?0?
1

出力例 2

文字列 TT' として考えられるものは 000, 001, 100, 10144 通りです。


入力例 3

10111?10??1101??1?00?1?01??00010?0?1??
998244353

出力例 3

235562598

答えは非常に大きくなることがあるので、 (109+7)(10^9+7) で割った余りを求めてください。