Login
—
Dark mode
CSES Problem Set
Counting Tilings
Task
Statistics
CSES - Counting Tilings
Time limit:
1.00 s
Memory limit:
512 MB
Your task is to count the number of ways you can fill an $n \times m$ grid using $1 \times 2$ and $2 \times 1$ tiles.
Input
The only input line has two integers $n$ and $m$.
Output
Print one integer: the number of ways modulo $10^9+7$.
Constraints
$1 \le n \le 10$
$1 \le m \le 1000$
Example
Input:
4 7
Output:
781
Dynamic Programming
...
Money Sums
Removal Game
Two Sets II
Increasing Subsequence
Projects
Elevator Rides
Counting Tilings
Counting Numbers