Hints: https://atcoder.jp/contests/arc176/editorial/9845

If \(N \ge M\), we can transform \(2^N \equiv 2^N - 2^{N-M}(2^M - 2^K) \equiv 2^{N-(M-K)} (\bmod\ 2^M - 2^K)\), which allows us to replace \(N\) with \(N-(M-K)\). By repeating this operation, we can reduce it to the case where \(N < M\).

Then, if \(N,K = M-1\), we have \(2^N = 2^M - 2^K\), so the answer is \(0\). Otherwise, \(2^N < 2^M - 2^K\), so the answer is \(2^N \bmod 10\).

Therefore, this problem can be solved in \(\mathrm{O}(\log N)\) or \(\mathrm{O}(1)\) time per test case.

Sample Implementation