题目描述

我们有一个由 0、1 和 ? 组成的字符串 $S$。令 $T$ 为 $S$ 的 $K$ 个副本的拼接。
通过用 0 或 1 替换 $T$ 中的每个 ?，我们可以获得 $2^{Kq}$ 个字符串，其中 $q$ 是 $S$ 中的 ? 的数量。对每个字符串解决下面的问题，并找到所有答案的和，对 $(10^9+7)$ 取模。

令 $T'$ 是用 ? 替换 $T$ 得到的字符串。我们将重复执行下面的操作，使所有 $T$ 中的字符相同。至少需要多少次操作？

• 选择整数 $l$ 和 $r$，使得 $1 \le l \le r \le |T'|$，并将 $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

?0?
1

示例输出 2

3

我们有四个 $T'$ 的候选：000、001、100 和 101。

示例输入 3

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

示例输出 3

235562598

由于答案可能很大，对 $(10^9+7)$ 取模后输出。