TUMSO18-K: Treasure

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const lli Mod = 98765431;
const int logN = 60;
lli mat11[logN + 5], mat12[logN + 5], mat21[logN + 5], mat22[logN + 5], pw[logN + 5];

int main(){

    mat12[0] = 2, mat11[0] = mat22[0] = mat21[0] = 1;

    for(int i=1;i<=logN;i++){
        mat11[i] = ( (mat11[i - 1] * mat11[i - 1]) % Mod + (mat12[i - 1] * mat21[i - 1]) % Mod ) % Mod;
        mat12[i] = ( (mat11[i - 1] * mat12[i - 1]) % Mod + (mat12[i - 1] * mat22[i - 1]) % Mod ) % Mod;
        mat21[i] = ( (mat21[i - 1] * mat11[i - 1]) % Mod + (mat22[i - 1] * mat21[i - 1]) % Mod ) % Mod;
        mat22[i] = ( (mat21[i - 1] * mat12[i - 1]) % Mod + (mat22[i - 1] * mat22[i - 1]) % Mod ) % Mod;
    }

    pw[0] = 1;
    for(int i=1;i<=logN;i++)
        pw[i] = (2 * pw[i - 1]);

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

    for(int q=1;q<=Q;q++){
        lli n;
        scanf("%lld", &n);

        lli one = 1, two = 1;
        for(lli i=0;i<=logN;i++){
            if(pw[i] & n){
                lli cur_one = ( (mat21[i] * two) % Mod + (mat22[i] * one) % Mod ) % Mod;
                lli cur_two = ( (mat11[i] * two) % Mod + (mat12[i] * one) % Mod ) % Mod;
                one = cur_one, two = cur_two;
            }
        }

        printf("%lld\n", two);
    }

    return 0;
}