Fun with Stones

#include <bits/stdc++.h>
using namespace std;

typedef pair<int64_t, int64_t> ll;

const int64_t MOD = 1e9+7;

int64_t extended_gcd(int64_t a, int64_t b, int64_t &x, int64_t &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int64_t g = extended_gcd(b, a%b, y, x);
    y -= x*(a/b);
    return g;
}

int64_t inv_mod(int64_t a, int64_t m = MOD) {
  int64_t x, y;
  extended_gcd(a, m, x, y);
  return (x%m + m)%m;
}

string toBinary(int64_t x) {
  string a;
  for (int i = 0; i < 30; ++i) {
    if (x & (1 << i)) {
      a = '1' + a;
    } else {
      a = '0' + a;
    }
  }
  return a;
}

int mxSz;
int l1, l2, l3;
int r1, r2, r3;
string s1, s2, s3;
string s11, s22, s33;

ll dp[30][2][2][2][2][2][2][2];
bool used[30][2][2][2][2][2][2][2];

ll solve(int idx, bool xxor, bool top1, bool top2, bool top3, bool bot1, bool bot2, bool bot3) {
  if (idx == 30) {
    return xxor ? ll{0, 1} : ll{1, 0};
  }

  if (used[idx][xxor][top1][top2][top3][bot1][bot2][bot3]) {
    return dp[idx][xxor][top1][top2][top3][bot1][bot2][bot3];
  }

  used[idx][xxor][top1][top2][top3][bot1][bot2][bot3] = true;

  ll ans{0, 0};

  int mx1 = top1 ? 1 : s1[idx]-'0';
  int mn1 = bot1 ? 0 : s11[idx]-'0';
  for (int i = mn1; i <= mx1; ++i) {
    int mx2 = top2 ? 1 : s2[idx]-'0';
    int mn2 = bot2 ? 0 : s22[idx]-'0';
    for (int j = mn2; j <= mx2; ++j) {
      int mx3 = top3 ? 1 : s3[idx]-'0';
      int mn3 = bot3 ? 0 : s33[idx]-'0';
      for (int k = mn3; k <= mx3; ++k) {
        // cout << i << ' ' << j << ' ' << k << '\n';
        ll res = solve(idx + 1, xxor | (i xor j xor k), top1 | (i != mx1), top2 | (j != mx2), top3 | (k != mx3), bot1 | (i != mn1), bot2 | (j != mn2), bot3 | (k != mn3));
        ans.first = (ans.first + res.first) % MOD;
        ans.second = (ans.second + res.second) % MOD;
      }
    }
  }

  return dp[idx][xxor][top1][top2][top3][bot1][bot2][bot3] = ans;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  cin >> l1 >> r1 >> l2 >> r2 >> l3 >> r3;

  s1 = toBinary(r1);
  s2 = toBinary(r2);
  s3 = toBinary(r3);

  s11 = toBinary(l1);
  s22 = toBinary(l2);
  s33 = toBinary(l3);

  // cout << s1 << '\n';
  // cout << s2 << '\n';
  // cout << s3 << '\n';
  // cout << s11 << '\n';
  // cout << s22 << '\n';
  // cout << s33 << '\n';

  ll ans = solve(0, 0, 0, 0, 0, 0, 0, 0);

  // cout << ans.first << ' ' << ans.second << '\n';

  int64_t tot = (ans.first + ans.second) % MOD;

  int64_t res = (ans.second * inv_mod(tot, MOD)) % MOD;

  cout << res << '\n';

}