题目描述

青正在观测一个由基础粒子组成的元序列 $S$，由 0，1 或 ? 组成，然后这个元序列进行了一次展开，由 $S$ 的 $K$ 份复制串联得到了新序列 $T$。

序列中为 ? 的粒子会等概率地坍缩到 0 或 1，设 $q$ 为元序列 $S$ 中为 ? 的粒子数量，青想知道在 $2^{Kq}$ 种可能中，每种可能他需要最少用多少次区间翻转操作才能将序列变为全相同。

你只需帮助青计算所有可能的最少操作次数总和模 $10^9+7$ 即可。

一次区间翻转操作的定义为：

• 令 $T'$ 为坍缩后的序列，选择整数 $l,r$ 使得 $1 \leq l \leq r \leq |T'|$，然后使序列的第 $l \sim r$ 个粒子 0 变为 1，1 变为 0。

约束条件

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

输入格式

输入格式如下：

$S$
$K$

输出格式

输出答案。

输入输出样例 #1

输入 #1

101
2

输出 #1

2

输入输出样例 #2

输入 #2

?0?
1

输出 #2

3

输入输出样例 #3

输入 #3

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

输出 #3

235562598

样例解释 1

$T$ 为 101101，可以先把它变为 110011，再变为 111111，需要最少 $2$ 次区间翻转操作。