[1117 D](https://codeforces.com/problemset/problem/1117/D) matrix exponentiation DP! interesting
1117 D
matrix exponentiation DP! interesting