Let ~a_i~ be the number of baby crabs that are ~i~ months old, and let ~a_T~ be the number of crabs that are adults. The transition from month ~k~ to month ~k+1~ is given by:

$$\displaystyle \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{T-1} \\ a_T \end{bmatrix} \mapsto \begin{bmatrix} K a_T \\ a_1 \\ a_2 \\ \vdots \\ a_{T-2} \\ a_{T-1} + a_T \end{bmatrix}$$

Subtask 1

For 20% of points, we can implement this transition directly with two nested for loops.

Time Complexity: ~\mathcal O(NT)~

Subtask 2

For the remaining 80% of points, we note the transformation is linear, and we can represent it with the matrix ~A~:

$$\displaystyle A = \begin{bmatrix} 0 & 0 & \cdots & 0 & 0 & K \\ & & & & & 0 \\ & & & & & 0 \\ & & I & & & \vdots \\ & & & & & 0 \\ & & & & & 1 \end{bmatrix}$$

where ~I~ is the ~T \times T~ identity matrix.

Then we can obtain the answer with

$$\displaystyle A^{N-1}\begin{bmatrix} 0 \\ \vdots \\ 0 \\ C \end{bmatrix}$$

We can compute ~A^{N-1}~ quickly using binary exponentiation.

Time Complexity: ~\mathcal O(T^3\log N)~