Qhy is a lovely little girl who likes playing video games. She likes playing cytus, deemo and lovely, but her level is very limited. She wants to quickly improve her video game posture, but qhy usually doesn't have time to play at school, so she plans to set a goal for herself

In order to describe the level of qhy, we recorded the ability values of qhy on the i day of the three audio games as Ai, Bi and Ci respectively. Qhy found the law of the change of her ability value with the number of days through statistics: in weekly units, qhy can't play audio games in school from Monday to Saturday, and her ability value recurrence formula will be as follows:

Ai​=xa1​Ai-1​+ya1​

Bi​=xb1​Bi−1​+yb1​

Ci​=xc1​Ci−1​+yc1​

On Sundays qhy, she can practice music games at home. The recursive formulas of her ability values are:

Ai​=xa2​Ai−1​+ya2​

Bi​=xb2​Bi−1​+yb2​

Ci​=xc2​Ci−1​+yc2​

A more magical thing is that qhy's ability values will change positions after three weeks. For example, after the end of Sunday in the third week, qhy's three ability values will change positions like this:

Ai​=Bi​,Bi​=Ci​,Ci​=Ai​

Now qhy has q queries, and each query contains an N, which indicates the three ability values of qhy after n days of inquiry, so that she can set goals in combination with her actual situation. For convenience, the three initial ability values are 0, which may be very large. Please put the result mod # 19260817.

Note: if the inquiry is just three weeks, please output the result after the capability value is changed

In the first line, there are three positive integers xa1, xb1 and xc1. The meaning is shown in the title

In the second line, there are three positive integers ya1, yb1 and yc1. The meaning is shown in the title

In the third line, there are three positive integers xa2, xb2 and xc2. The meaning is shown in the title

In the fourth line, there are three positive integers ya2, yb2 and yc2. The meaning is shown in the title

The fifth line is a positive integer q, which represents the number of queries

The next q lines, each with a positive integer ni, represent each query.

q lines, each line outputs the answer of each query

For 30% data, n < = 10 ^ 6

For 100% data, n < = 10 ^ 9, Q < = 10, x, y < = 10 ^ 9

Deduce the matrix ↓ (x,y can be modified according to the situation, and the answer is at position (1,0))

It's OK to calculate the solution of the first 63 days in advance

#include<iostream>
#include<cstring>
#include<cstdio>
#define Mod 19260817
using namespace std;
struct node{
    long long m[5][5];
    node(){memset(m,0,sizeof(m));};
}a,b,c,a7,b7,c7,A[71],B[71],C[71];
node matrix(node X,node Y){//Matrix multiplication template
    node ans;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int K=0;K<2;K++){
                ans.m[i][j]=(ans.m[i][j]+((X.m[i][K]*Y.m[K][j])%Mod))%Mod;
            }
        }
    }
    return ans;
}
node ksm(node x,int cs){
    node XX;
    XX.m[0][0]=1;
    XX.m[1][1]=1;
    for(int i=cs;i;i>>=1,x=matrix(x,x)){
        if(i&1) XX=matrix(XX,x);
    }
    return XX;
}
int main(){
    int xa1,xb1,xc1,ya1,yb1,yc1,xa2,xb2,xc2,ya2,yb2,yc2;
    scanf("%d%d%d",&xa1,&xb1,&xc1);
    scanf("%d%d%d",&ya1,&yb1,&yc1);
    scanf("%d%d%d",&xa2,&xb2,&xc2);
    scanf("%d%d%d",&ya2,&yb2,&yc2);
    a.m[0][0]=xa1;
    a.m[0][1]=0;
    a.m[1][0]=ya1;
    a.m[1][1]=1;
    b.m[0][0]=xb1;
    b.m[0][1]=0;
    b.m[1][0]=yb1;
    b.m[1][1]=1;
    c.m[0][0]=xc1;
    c.m[0][1]=0;
    c.m[1][0]=yc1;
    c.m[1][1]=1;
    
    a7.m[0][0]=xa2;
    a7.m[0][1]=0;
    a7.m[1][0]=ya2;
    a7.m[1][1]=1;
    b7.m[0][0]=xb2;
    b7.m[0][1]=0;
    b7.m[1][0]=yb2;
    b7.m[1][1]=1;
    c7.m[0][0]=xc2;
    c7.m[0][1]=0;
    c7.m[1][0]=yc2;
    c7.m[1][1]=1;
    
    A[0].m[0][0]=1;
    A[0].m[1][1]=1;
    B[0].m[0][0]=1;
    B[0].m[1][1]=1;
    C[0].m[0][0]=1;
    C[0].m[1][1]=1;
    for(int i=1;i<=21;i++){
        if(i%7==0) A[i]=matrix(A[i-1],a7);
        else A[i]=matrix(A[i-1],a);
    }
    for(int i=1;i<=21;i++){
        if(i%7==0) B[i]=matrix(B[i-1],b7);
        else B[i]=matrix(B[i-1],b);
    }
    for(int i=1;i<=21;i++){
        if(i%7==0) C[i]=matrix(C[i-1],c7);
        else C[i]=matrix(C[i-1],c);
    }
    node TTT;
    TTT=A[21];
    A[21]=B[21];
    B[21]=C[21];
    C[21]=TTT;
    for(int i=22;i<=42;i++){
        if(i%7==0) A[i]=matrix(A[i-1],a7);
        else A[i]=matrix(A[i-1],a);
    }
    for(int i=22;i<=42;i++){
        if(i%7==0) B[i]=matrix(B[i-1],b7);
        else B[i]=matrix(B[i-1],b);
    }
    for(int i=22;i<=42;i++){
        if(i%7==0) C[i]=matrix(C[i-1],c7);
        else C[i]=matrix(C[i-1],c);
    }
    TTT=A[42];
    A[42]=B[42];
    B[42]=C[42];
    C[42]=TTT;
    for(int i=43;i<=63;i++){
        if(i%7==0) A[i]=matrix(A[i-1],a7);
        else A[i]=matrix(A[i-1],a);
    }
    for(int i=43;i<=63;i++){
        if(i%7==0) B[i]=matrix(B[i-1],b7);
        else B[i]=matrix(B[i-1],b);
    }
    for(int i=43;i<=63;i++){
        if(i%7==0) C[i]=matrix(C[i-1],c7);
        else C[i]=matrix(C[i-1],c);
    }
    TTT=A[63];
    A[63]=B[63];
    B[63]=C[63];
    C[63]=TTT;
    int T1;
    scanf("%d",&T1);
    while(T1--){
        int n;
        scanf("%d",&n);
        node AA,BB,CC;
        AA.m[0][0]=1;
        AA.m[1][0]=0;
        AA.m[1][1]=1;
        BB.m[0][0]=1;
        BB.m[1][0]=0;
        BB.m[1][1]=1;
        CC.m[0][0]=1;
        CC.m[1][0]=0;
        CC.m[1][1]=1;
        int N;
        if(n/63>0){
            N=n%63;
            AA=ksm(A[63],n/63);
            BB=ksm(B[63],n/63),
            CC=ksm(C[63],n/63);
        }
        else N=n;
        for(int i=1;i<=N;i++){
            if(i%7==0){
                AA=matrix(AA,a7);
                BB=matrix(BB,b7);
                CC=matrix(CC,c7);
            }
            else{
                AA=matrix(AA,a);
                BB=matrix(BB,b);
                CC=matrix(CC,c);
            }
            if(i%21==0){
                node TT;
                TT=AA;
                AA=BB;
                BB=CC;
                CC=TT;
            }
        }
        cout<<AA.m[1][0]<<" "<<BB.m[1][0]<<" "<<CC.m[1][0]<<endl;
    }
}