#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e6 + 9, Mod = 1e9 + 7, inv2 = 5e8 + 4; int fpow(int a, int b = Mod - 2) { int res = 1; while (b) { if (b & 1) res = 1ll * res * a % Mod; a = 1ll * a * a % Mod, b >>= 1; } return res; } int n, q, opt, pw[N], ip[N], F[N], S[2][N], iS[2][N], spw[N], ispw[N], eqs[N]; bitset<N> s; int slv(int l, int r) { int res = ((F[r] - F[l - 1] - 1ll * S[0][l - 1] * (iS[0][r] - iS[0][l - 1] + Mod) % Mod - 1ll * S[1][l - 1] * (iS[1][r] - iS[1][l - 1] + Mod) % Mod) % Mod + Mod) % Mod * pw[r - l] % Mod; res = ((ll)res + eqs[r] - eqs[l] + Mod) % Mod; if (r - l >= 2) res = ((res + 1ll * (r - l - 1) * spw[r - l - 2] - ispw[r - l - 2]) % Mod + Mod) % Mod; return 1ll * res * inv2 % Mod; } signed main() { scanf("%d%d%d", &n, &q, &opt); pw[0] = ip[0] = spw[0] = 1; for (int i = 1; i <= n; i++) { pw[i] = (pw[i - 1] << 1) % Mod; ip[i] = 1ll * ip[i - 1] * inv2 % Mod; spw[i] = (spw[i - 1] + pw[i]) % Mod; ispw[i] = (ispw[i - 1] + 1ll * i * pw[i]) % Mod; } for (int i = 1; i <= n; i++) { int x; scanf("%1d", &x); s[i] = (bool)(x); } for (int i = 2; i <= n; i++) { eqs[i] = eqs[i - 1] + (s[i] == s[i - 1]); } for (int i = 1; i <= n; i++) { S[0][i] = S[0][i - 1], S[1][i] = S[1][i - 1]; (S[s[i]][i] += pw[i]) %= Mod; iS[0][i] = iS[0][i - 1], iS[1][i] = iS[1][i - 1]; (iS[s[i]][i] += ip[i]) %= Mod; } for (int i = 1; i <= n; i++) { F[i] = (F[i - 1] + 1ll * S[s[i]][i - 1] * ip[i]) % Mod; } int AL, BL, AR, BR, LI, RI, ans = 0; if (opt) scanf("%d%d%d%d%d%d", &AL, &BL, &AR, &BR, &LI, &RI); for (int I = 1; I <= q; I++) { int l, r; if (opt) { l = (1ll * AL * LI + BL) % n + 1, r = (1ll * AR * RI + BR) % n + 1; if (l > r) swap(l, r); LI = l, RI = r; } else scanf("%d%d", &l, &r); if (opt) ans ^= (slv(l, r) + 23 * I); else printf("%d\n", slv(l, r)); } if (opt) printf("%d\n", ans); return 0; }