Tiling 2xN with Dominoes and L-Trominoes
combinatorics matrix-exponentiation
Count the tilings of a 2×N board using 2×1 dominoes AND L-shaped trominoes, modulo 109+7. The recurrence is f(N)=f(N−1)+f(N−2)+2g(N−1), g(N)=f(N−1)+g(N−1); track both.
Input: one integer N.
Output: the count modulo 109+7.
Constraints:
- 1 ≤ N ≤ 1018
Sample Tests
Input 1
1
Output 1
1
Input 2
2
Output 2
4
Input 3
3
Output 3
9
Input 4
4
Output 4
25
Discussion (opens after you solve — no spoilers before)
No comments yet.