# ABC129 E. Sum Equals Xor

I solved it by digit DP with ordering monoid. In this DP, we scan the digits from the lowest to the highest as maintaining (order, carry). Iwarete mireba a+b=(a^b)+2*(a&b) kizuku beki.

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

struct mint {
int n;
mint(int n_ = 0) : n(n_) {}
};

mint operator-(mint a) {
return -a.n + MOD * (a.n != 0);
}
mint operator+(mint a, mint b) {
int x = a.n + b.n;
return x - (x >= MOD) * MOD;
}
mint operator-(mint a, mint b) {
int x = a.n - b.n;
return x + (x < 0) * MOD;
}
mint operator*(mint a, mint b) {
return (long long)a.n * b.n % MOD;
}
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
istream &operator>>(istream &i, mint &a) { return i >> a.n; }
ostream &operator<<(ostream &o, mint a) { return o << a.n; }

mint dp[100003][3][2]; // EQ, LT, GT

enum { EQ, LT, GT };

int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
string s;
cin >> s;
const int n = s.size();
dp[n][EQ][0] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 2; k++) {
for (int x = 0; x < 2; x++) {
for (int y = 0; y < 2; y++) {
int v = x + y + k;
int u = v % 2;
if ((x ^ y) != v % 2) continue;
int nj = j;
if (s[i] - '0' < u) nj = GT;
if (s[i] - '0' > u) nj = LT;
dp[i][nj][v / 2] += dp[i + 1][j][k];
}
}
}
}
}
cout << dp[0][LT][0] + dp[0][EQ][0] << endl;
}