**Problem link** : contest

practice

**Difficulty** : Hard

**Pre-requisites** : Matrix exponentiation, dp

**Solution** :

- When X = 1, You can do a simple dp. For optimizing that dp, you need to use matrix exponentiation.
- When X = 2, Idea is similar, but this time rows and coloumns of matrix will be larger.
- When X = 3, You can notice that matrix created will be sparse, You can use this observation very well. As N is very small. Assume you want to compute A^n where n is small. Note that we will

keep multiplying A by A, then A^2 by A, then A^3 by A, In the process we are always doing a multiplication by a sparse matrix.

You can also do a dp here too. You don’t need matrix exponentiation too.

**Setter’s solution**: link