Wide Path Paving
Medium · dynamic programming
A garden path is 3 squares wide and n squares long, so it is a grid of 3 rows and n columns of unit squares. You are paving it with stone slabs. Every slab covers exactly two squares that share a side, so a slab lies either left to right (two squares in one row) or up and down (two squares in one column).
The path must be covered completely: every square is under exactly one slab, and no slab overlaps another or sticks out of the path.
Return how many different ways there are to pave the path, modulo 10^9 + 7. Two ways are different if some square is covered by a slab together with a different neighbour. All slabs look alike. Return 0 if the path cannot be paved.
Examples
Example 1
Input: n = 2
Output: 3
There are three ways. Three slabs lie left to right, one in each row. Or the top two rows are filled with two slabs standing up and down and the bottom row has one slab lying left to right. Or the same with the rows turned over.
Example 2
Input: n = 3
Output: 0
A path 3 long has 9 squares, an odd number, and every slab covers 2 squares, so it cannot be paved.
Example 3
Input: n = 4
Output: 11
Constraints
- 1 <= n <= 100000