### 题目大意

$|R|\le 10^6,n\le 7$.

### 解题思路

$$\sum_{S}(-1)^{|S|}h(\text{奇数点连通块数目})\cdot R^{\text{偶数点连通块数目}}$$

$$f(n)=g(n)-\sum_{i=1}^n\binom{n-1}{i-1}\cdot f(i)\cdot g(n-i)$$

### 代码

void check(int m){
int sum = 1, siz[2]{};
lfor(i, 1, m) sum = 1ll * sum * f[cnt[i]] % mod, ++siz[cnt[i] & 1];
sum = 1ll * sum * qpow(suf[mk], siz[0]) % mod;
sum = 1ll * sum * h[siz[1]] % mod;
MOD(Ans += sum - mod);
}
void Dfs(int x, int idcnt){
if(x > n) return check(idcnt);
lfor(i, 1, idcnt) ++cnt[i], Dfs(x + 1, idcnt), --cnt[i];
++cnt[idcnt + 1], Dfs(x + 1, idcnt + 1), --cnt[idcnt + 1];
}

signed main(){
scanf("%s", s + 1), m = strlen(s + 1), mk = m * k;
lfor(i, 1, m) s[i] -= '0';
lfor(i, 0, k - 1) lfor(j, 1, m) s[i * m + j] = s[j];
reverse(s + 1, s + mk + 1);
lfor(i, 1, mk){
pw[i] = 2ll * pw[i - 1] % mod;
MOD(suf[i] = suf[i - 1] + s[i] * pw[i - 1] % mod - mod);
}

bool have_one = 0; h[0] = 1;
rfor(i, mk, 1) if(s[i]){
memset(dp, 0, sizeof dp), dp[0][0][0] = 1;
lfor(j, 1, n){
lfor(a, 0, 1) lfor(b, 0, 1){
MOD(dp[j][1][b] += 1ll * dp[j - 1][a][b] * (a ? pw[i - 1] : 1) % mod - mod);
MOD(dp[j][a][b ^ 1] += 1ll * dp[j - 1][a][b] * suf[i - 1] % mod - mod);
}
if(j % 2 == 0 || have_one == 0) MOD(h[j] += dp[j][1][0] - mod);
}
have_one |= s[i];
}

f[1] = g[1] = 1;
lfor(i, 1, n) lfor(j, 1, i - 1)
MOD(f[i] -= 1ll * C(i - 1, j - 1) * f[j] % mod * g[i - j] % mod);

Dfs(1, 0);

cout << 1ll * Ans * ifac[n] % mod << endl;
return 0;
}