long xorAndSum(string a, string b) {
    a.insert(0, 414159 - a.size(), '0');
    long result = 0, mod = 1000000007;
    vector<long> twoPower = { 1 }, aPartial = {0, a.back()-'0'};
    for (int i = 1; i < 414159; i++) {
        twoPower.push_back((2 * twoPower.back()) % mod);
        aPartial.push_back((aPartial.back() + (a[414158 - i] - '0') * twoPower.back()) % mod);
    }
    for (int i=0; i <= 314159; i++) result = (result + aPartial[i] + aPartial[414159] - aPartial[i+b.size()]) % mod;
    vector<vector<long>> cache = { {0, 0} };
    for (int i = 0; i <= 314159; i++) {
        cache[0][0] = (cache[0][0] + ((a[414158 - i] - '0') ^ 0) * twoPower[i]) % mod;
        cache[0][1] = (cache[0][1] + ((a[414158 - i] - '0') ^ 1) * twoPower[i]) % mod;
    }
    for (int i = 0; i < b.size(); i++) {
        result = (result + cache[i][b[b.size() - 1 - i] - '0']) % mod;
        long zero = (cache[i][0] - ((a[414158 - i] - '0') ^ 0) * twoPower[i]) % mod;
        long one = (cache[i][1] - ((a[414158-i] - '0') ^ 1) * twoPower[i] + twoPower[i+314160]) % mod;
        cache.push_back({zero, one});
    }
    return (result + mod) % mod;
}