显然的策略：选择全部 \(0\) 段变成 \(1\)，或选择全部 \(1\) 段变成 \(0\)。
归纳可得一般性的结论：设字符串中 \(s_i \ne s_{i+1}\) 的位置数为 \(k\)，答案为 \(\left\lceil\frac{k}{2}\right\rceil\)。
因为在模意义下不能上取整，考虑记 \(k\) 的奇偶性（这样统计答案的时候就知道答案是 \(\frac{k}{2}\) 还是 \(\frac{k+1}{2}\)），然后 dp。设 \(f_{i,0/1,0/1}\) 为前 \(i\) 个字符中，\(k\) 的奇偶性，\(s_i\) 填的数，\(k\) 的总和。类似地设 \(g_{i,0/1,0/1}\) 表示方案数。转移是 trivial 的。
因为 \(K \le 10^9\)，考虑把转移写成 \(8 \times 8\) 的矩阵乘法形式，预处理第一个 copy 的 dp 值，做一遍矩阵快速幂就行。
时间复杂度 \(O(n + 8^3 \log K)\)。
code
// Problem: F - Minflip Summation
// Contest: AtCoder - KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200）
// URL: https://atcoder.jp/contests/abc200/tasks/abc200_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 100100;
const ll mod = 1000000007;
const ll inv2 = (mod + 1) / 2;
struct matrix {
ll a[8][8];
matrix() {
mems(a, 0);
}
} ma[maxn], I;
inline matrix operator * (const matrix &a, const matrix &b) {
matrix res;
for (int i = 0; i < 8; ++i) {
for (int j = 0; j < 8; ++j) {
for (int k = 0; k < 8; ++k) {
res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j] % mod) % mod;
}
}
}
return res;
}
inline matrix qpow(matrix a, ll p) {
matrix res = I;
while (p) {
if (p & 1) {
res = res * a;
}
a = a * a;
p >>= 1;
}
return res;
}
int n, m, id[2][2][2];
ll f[maxn][2][2], g[maxn][2][2];
char s[maxn];
void solve() {
for (int i = 0; i < 8; ++i) {
I.a[i][i] = 1;
}
scanf("%s%d", s + 1, &m);
n = strlen(s + 1);
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
id[i][j][k] = i * 4 + j * 2 + k;
}
}
}
if (s[1] == '0' || s[1] == '?') {
g[1][0][0] = 1;
}
if (s[1] == '1' || s[1] == '?') {
g[1][0][1] = 1;
}
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < 2; ++j) {
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
if (s[i] != '?' && s[i] != '0' + y) {
continue;
}
int nj = j ^ (x ^ y);
f[i][nj][y] = (f[i][nj][y] + f[i - 1][j][x]) % mod;
if (x ^ y) {
f[i][nj][y] = (f[i][nj][y] + g[i - 1][j][x]) % mod;
}
g[i][nj][y] = (g[i][nj][y] + g[i - 1][j][x]) % mod;
}
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 2; ++j) {
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
if (s[i] != '?' && s[i] != '0' + y) {
continue;
}
int nj = j ^ (x ^ y);
++ma[i].a[id[0][j][x]][id[0][nj][y]];
if (x ^ y) {
++ma[i].a[id[1][j][x]][id[0][nj][y]];
}
++ma[i].a[id[1][j][x]][id[1][nj][y]];
}
}
}
}
matrix a = I, b;
for (int i = 1; i <= n; ++i) {
a = a * ma[i];
}
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
b.a[0][id[0][i][j]] = f[n][i][j];
b.a[0][id[1][i][j]] = g[n][i][j];
}
}
matrix res = b * qpow(a, m - 1);
ll ans = 0;
for (int i = 0; i < 2; ++i) {
ans = (ans + (res.a[0][id[0][1][i]] + res.a[0][id[1][1][i]]) % mod * inv2 % mod) % mod;
ans = (ans + res.a[0][id[0][0][i]] * inv2 % mod) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}