\(N^M \bmod{10}\) の値を知りたいので, \(N\) は下一桁しか関係しない. \(N^i \bmod{10}\) がどうなるかを計算してみると, 以下のようになる.

  1 2 3 4 5
0 0 0 0 0 0
1 1 1 1 1 1
2 2 4 8 6 2
3 3 9 7 1 3
4 4 6 4 6 4
5 5 5 5 5 5
6 6 6 6 6 6
7 7 9 3 1 7
8 8 4 2 6 8
9 9 1 9 1 9

上の表の通り, すべての数値は周期4で循環しているので, \(M\) を \(4\) で割った余りが分かればいい. \(4\) で割った余りは下2桁が分かれば計算できる.

なお, \(M = 0\) のときは \(N^0 = 1\) となる.