记录编号	618769	评测结果	AAAAAAAAAA
题目名称	4489.魔力数字	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	3.843 s
提交时间	2026-09-11 20:39:49	内存使用	127.43 MiB

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e7 + 10;;
const int Mod = 1e9 + 7;

string str;
long long a;
int len;
long long energy[N];
long long dp[N][2];
long long one_sum;
long long one_now;
long long res;

int main () {
    
    freopen ("math.in", "r", stdin);
    freopen ("math.out", "w", stdout);
    
    cin >> str >> a;
    
    len = str.size();
    
    for (int i = 0; i < len; i++) {
        if (str[i] == '1') {
            one_sum++;
        }
    }
    
    energy[1] = 1;
    for (int i = 2; i <= len; i++) {
        energy[i] = (energy[i - 1] * a % Mod + energy[i - 2]) % Mod;
    }
    
    dp[len + 1][1] = 1;
    for (int i = len; i >= 1; i--) {
        dp[i][0] = (dp[i + 1][0] + dp[i + 1][1]) % Mod;
        dp[i][1] = (dp[i + 1][0] + dp[i + 1][1] * (a + 1) % Mod) % Mod;
        
        if (str[i - 1] == '1') {
            one_now++;
            long long num = one_sum - one_now;
            res += (energy[num] * dp[i + 1][1] % Mod + (num ? energy[num - 1] : 1) * dp[i + 1][0] % Mod) % Mod;
            res %= Mod;
        }
    }
    res += energy[one_sum];
    res %= Mod;
    
    cout << res << endl;
    
    return 0;
}