Splitting Cells

Difficulty: 1700 4000 ms 128 MB

math matrix-exponentiation

Each generation, every mature cell splits into a mature cell plus an immature one, and every immature cell matures. Starting with one immature cell, count total cells after N generations, modulo 10⁹+7. (This is the Fibonacci growth.)

Input: one integer N.

Output: the value modulo 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

5

13

1

2

Read the Editorial