### PROBLEM LINK:

**Author:** Asif Haque

**Tester:** Jingbo Shang

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Medium

### PREREQUISITES:

Fast Matrix Power with Mod

### PROBLEM:

Given a m-order linear recurrence, calculate the n-th number (mod 10^9+7).

### EXPLANATION:

There are two key points in this problem:

Write the linear recurrence in matrix representation. That is using a m×m matrix to state one step of recurrence.

Fast calculate the matrix power operation. That is using O(m^3 logn) time to get A^n mod 10^9+7

Let’s take a example of Fibonacci Numbers.

fib[n] = fib[n - 1] + fib[n - 2]

This is a 2-order linear recurrence. And we can write this as the following matrix representation:

(fib[n-1],fib[n]) * (0, 1; 1, 1) = (fib[n], fib[n+1])

Here (0, 1; 1, 1) is a 2*2 matrix, denote as A.

After that, we need to calculate A^n mod 10^9+7.

We can prepare A^1,A^2,A^4…A^logn in O(m^3 logn) time. And then, multiple corresponding matrices together to get A^n. Based on the binary expression of n,it is obvious that these logn matrices will be multiplied at most once. Therefore, we can get the answer in O(m^3 logn).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.