Matrix<Mint>m(6,6);
m[0...5][0..5]=0;
m[0][0]=Mint(1)/Mint(3);
m[0][1]=Mint(2)/Mint(3);
m[1][2]=Mint(1)/Mint(2);
m[1][4]=Mint(1)/Mint(2);
m[2][2]=Mint(1)/Mint(3);
m[2][3]=Mint(2)/Mint(3);
m[3][0]=Mint(1)/Mint(2);
m[3][4]=Mint(1)/Mint(2);
m[4][4]=Mint(1)/Mint(3);
m[4][5]=Mint(2)/Mint(3);
m[5][0]=Mint(1)/Mint(2);
m[5][2]=Mint(1)/Mint(2);

ll@t;
rep(t){
	ll@n;
	wt((m**n)[0][0]);
}