Claire loves drawing lines. She receives a sheet of paper with an $$$n \times n$$$ grid and begins drawing "lines" on it. Well—the concept of a "line" here is not what we usually think of. Claire refers each line to be a set of consecutive vertical grid cells. When she draws a line, these cells are all covered with black ink. Initially, all the cells are white, and drawing lines turns some of them black. After drawing a few lines, Claire wonders: how many ways she can color an additional white cell black so that the remaining white cells do not form a single connected component.

Two cells are directly connected if they share an edge. Two cells $$$x$$$ and $$$y$$$ are indirectly connected if there exists a sequence of cells $$$c_0, c_1, \ldots, c_k$$$ with $$$k > 1$$$ such that $$$c_0 = x$$$, $$$c_k = y$$$, and for every $$$i \in \{1, 2, \ldots, k\}$$$ the cells $$$c_i$$$ and $$$c_{i-1}$$$ are directly connected. A set of cells forms a single connected component if each pair of cells in the set is either directly or indirectly connected.

The grid has $$$n$$$ rows and $$$n$$$ columns, both indexed from $$$1$$$ to $$$n$$$. Claire will draw $$$q$$$ lines. The $$$i$$$-th line is drawn in the $$$y_i$$$-th column, from the $$$s_i$$$-th row to the $$$f_i$$$-th row, where $$$s_i \leq f_i$$$ for each $$$i \in \{1, 2, \ldots, q\}$$$. Note that the cells that are passed by at least one of the $$$q$$$ lines are colored black. The following figure shows an example of a $$$20\times 20$$$ grid with $$$q=67$$$ lines. The grid cells marked with red star symbols refer to the cells such that, if Claire colors that cell black, all white cells no longer form a single connected component.

You may assume that, after drawing the $$$q$$$ lines, the remaining white cells form a single connected component with at least three white cells.