ヒント \(\rightarrow\) https://atcoder.jp/contests/arc176/editorial/9825

\(N \ge M\) の場合、\(2^N \equiv 2^N - 2^{N-M}(2^M - 2^K) \equiv 2^{N-(M-K)} (\bmod\ 2^M - 2^K)\) という変形により \(N\) を \(N-(M-K)\) に置き換えることが出来ます。そしてこの操作を繰り返すことで \(N < M\) のケースに帰着することが出来ます。

すると、\(N,K = M-1\) の場合 \(2^N = 2^M - 2^K\) となるため答えは \(0\)、それ以外の場合は \(2^N < 2^M - 2^K\) となるため答えは \(2^N \bmod 10\) となります。

以上よりこの問題をテストケースあたり \(\mathrm{O}(\log N)\) や \(\mathrm{O}(1)\) で解くことが出来ます。

実装例