给定一个仅含 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$ 取模。