Matrix<Mint>a(36,36),b(1,36);{ll@k,@m,@n;rep(m){ll@x,@y,@z;a[--x*6+--y][6y+--z]=1;}b[0][0..5]=1;Mint A;A+=(b*a**(n-2))[0][6(0..5)];wt(A);}