Matrix<Mint>m(4,4);
m[0...3][0..3]=0;
m[0][0]=1;
m[0][3]=2;
m[1][0]=3;
m[2][2]=1;
m[2][1]=1;
m[2][3]=1;
m[3][2]=3;
m[0...3][0..3]/=3;
ll@t;
rep(t)wt((m**rd_ll())[0][0]);