Domino Tilings of 2xN

Difficulty: 1700 4000 ms 128 MB

combinatorics matrix-exponentiation

Count the ways to tile a 2×N board with 1×2 dominoes, modulo 10⁹+7.

Input: one integer N.

Output: the number of tilings mod 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

1

1

2

2

3

3

Read the Editorial