← 返回题目列表

AtCoder · abc200_f

F. Minflip 求和

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一个字符串 S 组成 0, 1,和 ?。让 T 是以下的串联 K 副本 S.
通过替换每个 ? in T 与 0 or 1,我们可以得到 2^{Kq} 字符串,其中 q 是数量 ?位于 S。针对每个字符串解决以下问题,并求出所有答案的总和(取模) (10^9+7).

让 T' 为替换后得到的字符串 ? in T。我们将重复执行下面的操作,使所有字符都出现在 T 相同。这至少需要多少次操作?

  • 选择整数 l 和 r 这样 1 \le l \le r \le |T'|,并反转 l-th 通过 r第一个字符 T:来自 0 和 1 反之亦然。

约束

  • 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).