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)$$$
You can do inclusion-exclusion, brute force on all $$$2^k$$$ subsets of constraints, and find the number of ways to break at least every constraint in this subset in $$$O(n+k)$$$ (I am not sure if it can be optimized to $$$O(1)$$$ or $$$O(\log n)$$$). If the size of the subset is even add it to the answer, otherwise subtract it from the answer
Total complexity: $$$O((n+k)\cdot 2^k)$$$, this should pass subtasks $$$1,2,3$$$. I have no idea how to optimize the $$$k$$$ 😂
How to be that strong
Solve
Using modular inverse and some visit arrays, yes it can be optimized to $$$O(2^k \cdot k + n\log \text{MOD)}$$$
This is a solution for small $$$k$$$ and large $$$n$$$
The main observation is that even tho you will have $$$2e5$$$ doors you will worst case only walk trough $$$n$$$ restrictioned paths, given that i think you can do something like $$$dp[i][j]$$$ — nr of ways to get to a door at level $$$i$$$ and walked so far restricted doors $$$j$$$, where $$$j$$$ could be an array or a hash if you find a smart bijective relation.