← 返回 bytedance 的题目列表Domino and Tromino Tiling
类型：online_judge
Given a 2 x N grid, you need to completely cover the grid using Domino and Tromino tiles. How many different ways can you do this? Return the answer modulo 10^9 + 7.
Input Format
An integer N, representing the length of the grid.
Output Format
One integer, representing the number of ways to cover the grid.
Sample Input
3
Sample Output
5
Constraints
1 ≤ N ≤ 1000
Example
Input
1