题目描述

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 に変更する。

输入格式

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

$S$ $K$

输出格式

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

题目大意

给定一个仅含 0，1 和 ? 的字符串 $S$ 和一个参数 $K$，将 $S$ 复制 $K$ 次得到字符串 $T$。
（即 $T=SSS...S$，共 $K$ 个 $S$）

你可以对 $T$ 进行若干次操作：每次选取一组 $l$ 和 $r$，将 $[l, r]$ 内所有 1 变为 0，所有 0 变为 1。求将 $T$ 中的所有字符变为同一种所需的最小操作次数。

特别地，字符 ? 代表此处还没有填上。? 处既可填 0 亦可填 1，但你需要将填 0 和 1 的方案都计入最后的贡献之中。
形式化地讲，若 $S$ 中有 $q$ 个字符为 ?，你需要计算所有 $2^{Kq}$ 种可能的字符串各自所需要的最小操作数，并将它们的总和作为最终答案。
若仍不理解，可以参考样例2。

答案对 $10^9+7$ 取模。

101
2

2

?0?
1

3

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

235562598

提示

制約

• $1\ \le\ |S|\ \le\ 10^5$
• $1\ \le\ K\ \le\ 10^9$

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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