Counting tilings - MarisaOJ: Marisa Online Judge

Counting tilings

Time limit: 1000 ms
Memory limit: 256 MB
Count the number of ways you can fill an $n×m$ grid using $1×2$ and $2×1$ tiles. ### Input - A single line contains 2 integers $n$ and $m$. ### Output - Print the number of way, modulo $10^9+7$. ### Constraints - $1 \le n \le 10^4$. - $1 \le m \le 5$. ### Example Input: ``` 7 4 ``` Output: ``` 781 ```