PROG-T1134: Sequence

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

typedef long long lli;

const int MD = 2553;
const int MS = 4;
const int logN = log2(1e18);

int bl[logN + 1][MS][MS], ans[2][MS];

int main(){

    int a, b, c, d, e, f, g, h, Q;
    scanf("%d%d%d%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f, &g, &h, &Q);
    vector<vector<int>> base = {{e, f, g, h}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}};
    for(int i = 0; i < MS; ++i){
        for(int j = 0; j < MS; ++j){
            bl[0][i][j] = base[i][j];
        }
    }
    for(int e = 1; e <= logN; ++e){
        for(int i = 0; i < MS; ++i){
            for(int j = 0; j < MS; ++j){
                for(int k = 0; k < MS; ++k){
                    bl[e][i][j] = (bl[e][i][j] + bl[e - 1][i][k] * bl[e - 1][k][j]) % MD;
                }
            }
        }
    }
    while(Q--){
        lli x;
        scanf("%lld", &x);
        if(x <= 4){
            if(x == 1){
                cout << a << '\n';
            } else if(x == 2){
                cout << b << '\n';
            } else if(x == 3){
                cout << c << '\n';
            } else if(x == 4){
                cout << d << '\n';
            }
            continue;
        }
        x -= 4;
        ans[0][0] = d;  ans[0][1] = c;
        ans[0][2] = b;  ans[0][3] = a;
        int cur = 1;
        for(int e = logN; e >= 0; --e){
            if(x >= ((lli)1 << e)){
                int prv = cur ^ 1;
                for(int i = 0; i < MS; ++i){
                    ans[cur][i] = (ans[prv][0] * bl[e][i][0] + ans[prv][1] * bl[e][i][1] +
                                    ans[prv][2] * bl[e][i][2] + ans[prv][3] * bl[e][i][3]) % MD;
                }
                x -= ((lli)1 << e);
                cur ^= 1;
            }
        }
        cout << ans[cur ^ 1][0] << '\n';
    }

    return 0;
}