1403. Profile Dynamic Programming on Grid (Bitmask)

Count the number of ways to tile a rows by cols grid completely with 1x2 dominoes (each domino covers two orthogonally adjacent cells, placed horizontally or vertically). Return the count modulo 1000000007. If the number of cells is odd the answer is 0.

Input: A JSON object {"rows": <grid height>, "cols": <grid width>}.

Output: Return the number of domino tilings modulo 1000000007.

Examples

Input: {"rows":2,"cols":3}
Output: 3
Explanation: There are 3 domino tilings of a 2x3 grid.

Input: {"rows":3,"cols":3}
Output: 0
Explanation: Nine cells cannot be tiled by dominoes -> 0.

Constraints

• 1 <= rows, cols <= 12
• tiling is impossible when rows * cols is odd

Asked by