Actually I think it should belong to category of 'Bits Manipulation'.. but still, a really good one.

My first reaction was, how to derive from a ^ (b << i) from a ^ (b << (i - 1)), but after some thoughts, I figured out that that should not be the way to go: there's no easy way to do that induction. 

This one resembles with another Bit one: we are to calculate sum, so we consider bit by bit: at bit[i], it contributes bit[i] << i to the final sum..

Lesson learnt: 1) power2 can be moduled too; 2) VISUALIZE the problem space\process in your mind - it is crucial.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define MOD 1000000007unsigned sum(vector
           
             &ones, int l, int r){ l = std::max(0, l); r = std::min(int(ones.size() - 1), r); if (l > r) return 0; return ones[r] - (l == 0 ? 0 : ones[l - 1]);}int main() { const unsigned N = 314159; const unsigned NMAX = 1e6; string a, b; std::cin >> a >> b; std::reverse(a.begin(), a.end()); std::reverse(b.begin(), b.end()); // Power2 % MOD vector
            
              pw2(NMAX); pw2[0] = 1; for (unsigned i = 1; i < NMAX; i++) pw2[i] = (pw2[i - 1] * 2LL) % MOD; // Count accumulative count of ones size_t lena = a.length(); size_t lenb = b.length(); vector
             
               ones(lenb, 0); for (int i = 0; i < lenb; i++) { ones[i] = b[i] - '0'; if (i > 0) ones[i] += ones[i - 1]; } // Count accumulative count of zeros unsigned ans = 0; for (int i = 0; i < NMAX; i++) { int bita = (i >= lena) ? 0 : a[i] - '0'; int cnt_ones = sum(ones, i - N, i); if (bita) { ans = (unsigned)((ans + (N + 1 - cnt_ones) * 1LL * pw2[i]) % MOD); } else { ans = (unsigned)((ans + cnt_ones * 1LL * pw2[i]) % MOD); } } cout << ans << endl; return 0;}