Statement:

There are $$$n$$$ rooms numbered from $$$1$$$ to $$$n$$$, and there is an exit that lies after room $$$n$$$.
There are $$$a_i$$$ $$$(1 \le i < n)$$$ doors numbered from $$$1$$$ to $$$a_i$$$ connecting room $$$i$$$ to room $$$i+1$$$, and $$$a_n$$$ doors numbered from $$$1$$$ to $$$a_n$$$ connecting room $$$n$$$ and the exit.

Stanley starts at room $$$1$$$. Each time Stanley is at room $$$i$$$, he chooses one of the $$$a_i$$$ doors and goes through it to room $$$i+1$$$ (or to the exit if $$$i=n$$$).

Each time Stanely reaches the exit he gets an ending, and two endings are considered different if the path Stanely took in each of them is different (i.e. there exists a room $$$i$$$ such that Stanely choose different doors while he was in room $$$i$$$ in the two paths)

But there is a twist, there are $$$k$$$ constraints, the $$$j$$$-th $$$(1 \le j \le k)$$$ has $$$4$$$ values $$$x_{j,1}, y_{j,1}, x_{j,2}, y_{j,2}$$$ $$$(1 \le x_{j,1} < x_{j,2} \le n),$$$ $$$(1 \le y_{j,1} \le a_{x_{j,1}}),$$$ $$$(1 \le y_{j,2} \le a_{x_{j,2}}),$$$ meaning that if Stanely on his path took door $$$y_{j,1}$$$ while he was in room $$$x_{j,1}$$$, then he can't take door $$$y_{j,2}$$$ when he is at room $$$x_{j,2}$$$

Stanley wants to find the number of different endings he can get, since this number can be large he wants to find its value modulo $$$10^9 + 7$$$

Subtasks:

• Subtask $$$1$$$: $$$(1\le n \le 10),$$$ $$$(k = 0),$$$ $$$(1\le a_i \le 10)$$$

• Subtask $$$2$$$: $$$(1\le n \le 10),$$$ $$$(0\le k \le 10),$$$ $$$(1\le a_i \le 10)$$$

• Subtask $$$3$$$: $$$(1\le n \le 20),$$$ $$$(0\le k \le 20),$$$ $$$(1\le a_i \le 10^5)$$$

• Subtask $$$4$$$: $$$(1\le n \le 20),$$$ $$$(0\le k \le 2\times 10^5),$$$ $$$(1\le a_i \le 10^9)$$$