Grid Paths Through Required Cells

You are given two integers rows and cols describing a grid with rows rows and cols columns, and a list of cells required. Rows and columns are numbered from 0. Row 0 is the top row and column 0 is the leftmost column. Each element in required contains [r, c] meaning the cell in row r and column c.

A walk starts at the bottom-left cell (rows - 1, 0) and ends at the bottom-right cell (rows - 1, cols - 1). Each move goes to the next column and must stay inside the grid. From cell (r, c) a move can go to:

• (r - 1, c + 1), one row up
• (r, c + 1), the same row
• (r + 1, c + 1), one row down

A walk contains every cell it passes through, including its start and end cells. Note that when cols = 1 the only walk is the single cell (rows - 1, 0).

Return the number of walks that contain every cell in required. Mod the result by 10 ** 9 + 7.

Examples

Example 1

Input:  rows     = 3
        cols     = 3
        required = []
Output: 2
Explanation: Both walks start at (2, 0) and end at (2, 2). One stays in the bottom row:
(2, 0), (2, 1), (2, 2). The other goes up and comes back: (2, 0), (1, 1), (2, 2).
A walk that reaches row 0 in column 1 cannot get back to row 2 in one move.

Example 2

Only one of the two walks contains (1, 1).

Input:  rows     = 3
        cols     = 3
        required = [[1, 1]]
Output: 1
Explanation: Of the two walks above, only (2, 0), (1, 1), (2, 2) contains the cell (1, 1).

Example 3

Input:  rows     = 2
        cols     = 4
        required = [[0, 1],
                    [0, 2]]
Output: 1
Explanation: The walk must be in row 0 in columns 1 and 2, so it is
(1, 0), (0, 1), (0, 2), (1, 3). Without the required cells there would be 4 walks.

Example 4

Input:  rows     = 3
        cols     = 4
        required = [[0, 1]]
Output: 0
Explanation: The first move from (2, 0) can only reach row 1 or row 2, so no walk
contains (0, 1).