\(N^K \ \% \ 6\) を求めれば数字が求まる. これは \((N \ \% \ 6)^K \ \% \ 6\) で計算できる.

まずは \(N \ \% \ 6\) を考える. これは \(N \ \% \ 2, N \ \% \ 3\) を求めればいい. 2で割った余りは下一桁を見れば分かるし, 3で割った余りはすべての数字を足して3で割った余りである.

N%2 N%3 N%6
0 0 0
0 1 4
0 2 2
1 0 3
1 1 1
1 2 5

次に \((N \ \% \ 6)^K \ \% \ 6\) であるが, これは \(K\) を順に計算していくと以下のように周期2でループする.

N%6 1 2 3 4
0 0 0 0 0
1 1 1 1 1
2 4 2 4 2
3 3 3 3 3
4 4 4 4 4
5 1 5 1 5

よって \(K \ \% \ 2\) が分かれば \((N \ \% \ 6)^K \ \% \ 6\) が求まる.