Sequence j=1a+10b (j0=1,j1=2)

Difficulty: 1700 4000 ms 128 MB

math matrix-exponentiation

The sequence has j(0)=1, j(1)=2 and j(n)=1j(n−1)+10j(n−2). Print j(N) modulo 10⁹+7.

Input: one integer N.

Output: j(N) mod 10⁹+7.

Constraints:

• 0 ≤ N ≤ 10¹⁸

Sample Tests

4

152

0

1

1

2

Read the Editorial