Strings Without Adjacent Ones

Difficulty: 1500 4000 ms 128 MB

dp matrix-exponentiation

Count the binary strings of length N with no two adjacent 1s, modulo 10⁹+7.

Input: one integer N.

Output: the count mod 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

3

5

1

2

Read the Editorial