PROG-1134: Sequence

#include <bits/stdc++.h>

using namespace std;
const int mod = 2553;
using lli = long long;
int a, b, c, d, e, f, g, h;
int ar[65][4][4];
lli pow2[65];

int main(){

    scanf("%d%d%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f, &g, &h);

    ar[0][0][0] = e, ar[0][0][1] = f, ar[0][0][2] = g, ar[0][0][3] = h;
    ar[0][1][0] = ar[0][2][1] = ar[0][3][2] = 1;
    pow2[0] = 1;

    for(int idx=1;idx<=60;idx++){
        pow2[idx] = (lli) pow2[idx-1] * 2;
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                ar[idx][i][j] = 0;
                for(int k=0;k<4;k++){
                    ar[idx][i][j] += (ar[idx-1][i][k] * ar[idx-1][k][j]) % mod;
                    ar[idx][i][j] %= mod;
                }
            }
        }
    }

    int q;
    scanf("%d", &q);

    while(q --){
        lli n;
        scanf("%lld", &n);
        if(n == 1) printf("%d\n", a);
        else if(n == 2) printf("%d\n", b);
        else if(n == 3) printf("%d\n", c);
        else if(n == 4) printf("%d\n", d);
        else{
            int ans[4] = {d, c, b, a};
            n -= 4;
            for(int idx=0;idx<=60;idx++){
                if(pow2[idx] & n){
                    int keep[4];
                    keep[0] = ( ar[idx][0][0] * ans[0] + ar[idx][0][1] * ans[1] + ar[idx][0][2] * ans[2] + ar[idx][0][3] * ans[3]) % mod;
                    keep[1] = ( ar[idx][1][0] * ans[0] + ar[idx][1][1] * ans[1] + ar[idx][1][2] * ans[2] + ar[idx][1][3] * ans[3]) % mod;
                    keep[2] = ( ar[idx][2][0] * ans[0] + ar[idx][2][1] * ans[1] + ar[idx][2][2] * ans[2] + ar[idx][2][3] * ans[3]) % mod;
                    keep[3] = ( ar[idx][3][0] * ans[0] + ar[idx][3][1] * ans[1] + ar[idx][3][2] * ans[2] + ar[idx][3][3] * ans[3]) % mod;
                    for(int i=0;i<4;i++)
                        ans[i] = keep[i];
                }
            }
            printf("%d\n", ans[0]);
        }
    }

    return 0;
}