Source Code
#include <bits/stdc++.h>
using namespace std;
#define Yalahwy cin.tie(0), cout.tie(0), cin.sync_with_stdio(0), cout.sync_with_stdio(0);
#define ll long long
#define ld long double
#define EPS 1e-9
#define INF INT_MAX
#define pb push_back
#define pf push_front
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define rep(i, k, n) for(int i=k; i < n ; i++)
#define rev(i, n, k) for(int i = n; i>= k; i--)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define NIL -1

// alt + ctrl + l
// يا رب
const ll MOD = 1000000007;
const ll N = 1e6 + 5;
const ll C = 10;
//const ll K = 5;
const ll M = 10;
//const int OO=0x3f3f3f3f;
//const ll LOO=0x3f3f3f3f3f3f3f3f;
//int dx8[] = {+0, +0, -1, +1, +1, +1, -1, -1};
//int dy8[] = {-1, +1, +0, +0, +1, -1, +1, -1};
//int dx4[] = {+0, +0, -1, +1};
//int dy4[] = {-1, +1, +0, +0};
//struct cmp {
//    bool operator()(M const& p1, M const& p2)
//    {
//        return p1.dis > p2.dis;
//    }
//};
ll p_pow[N];
ll egcd(ll a, ll b, ll &x, ll &y){ /// ax + by = gcd(a,b)
    if(!b){
        x=1;
        y=0;
        return a;
    }
    ll g=egcd(b,a%b,y,x);
    y-=(a/b)*x;
    return g;
}

ll modInverse(ll a, ll m){ /// (a/b)%m = ((a%m)*(modInverse(b)%m))%m
    ll x,y,g;
    g=egcd(a,m,x,y);
    if(g>1)
        return -1;
    return (x+m)%m;
}
ll fixMod(ll a, ll p){
    return (a+p)%p;
}

ll pushBack(ll h1 , ll h2, ll xp, ll p){    // xp = x^(LenToPush(h2))
    return ((h1*xp)%p + h2)%p;
}

ll pushFront(ll h1, ll h2, ll xp, ll p){     // xp = x^(MainLen(h1))
    return (h1 + (h2*xp)%p)%p;
}

ll popFront(ll h1, ll h2, ll xp, ll p){  // xp=x^(MainLen(h1)-LenToPop(h2))
    return fixMod(h1 - (h2*xp)%p, p);
}

ll popBack(ll h1, ll h2, ll xp, ll p){  // xp=x^(LenToPop(h2))
    return (fixMod(h1 - h2, p) * modInverse(xp,p))%p;
}
vector<ll> h;

ll get(ll l, ll r, vector<ll>& H, ll xp, ll p){
    if(l==0) return H[r];
    ll val = popFront(H[r],H[l-1],xp, p);
    return val;
}

int main() {
    Yalahwy
    p_pow[0] = 1;
    ll p = 2, q;
    for (int i = 1; i <= 1e6 ; i++)
        p_pow[i] = (p_pow[i-1] * p) % MOD;
    string s;
    cin >> s >> q;
    h.resize(s.size());
    h[0] = pushBack(h[0], s[0] - '0', p, MOD);
    for (int i = 1; i < s.size(); ++i) {
        h[i] = pushBack(h[i - 1], s[i] - '0', p, MOD);
    }
    while (q--){
        ll l, r;
        cin >> l >> r;
        l--;
        r--;
        cout << get(l, r, h, p_pow[r - l + 1], MOD)%10<< endl;
    }
}

Copy
Binarithm Yalahwy
GNU G++17
458 ms
10.3 MB
Wrong Answer