P5469 [NOI2019] Robot.

Time limit: 3 seconds, memory limit: 512MB.

Little R likes studying robots. Recently, Little R developed two new types of robots, `P`-type robots and `Q`-type robots. Now he wants to test their moving abilities. The test is done on $n$ pillars arranged in a line from left to right, numbered $1 - n$ in order. The height of pillar $i$ is a positive integer $h_i$. Robots **can only move between adjacent pillars**, that is: if a robot is currently on pillar $i$, it can only try to move to pillar $i - 1$ and pillar $i + 1$. In each test, Little R chooses a starting point $s$ and places both types of robots on pillar $s$. Then they move according to their own rules. The `P`-type robot keeps moving **to the left**, but it **cannot** move onto a pillar that is **higher** than the starting pillar $s$. More specifically, the `P`-type robot stops at pillar $l \ (l \leq s)$ **if and only if** both of the following conditions hold: - $l = 1$ or $h_{l-1} > h_s$. - For every $j$ with $l \leq j \leq s$, we have $h_j \leq h_s$. The `Q`-type robot keeps moving **to the right**, but it **can only** move onto pillars that are **lower** than the starting pillar $s$. More specifically, the `Q`-type robot stops at pillar $r \ (r \geq s)$ **if and only if** both of the following conditions hold: - $r = n$ or $h_{r+1} \geq h_s$. - For every $j$ with $s < j \leq r$, we have $h_j < h_s$. Now, Little R can set the height of each pillar. The selectable height range for pillar $i$ is $[A_i, B_i]$, that is, $A_i \leq h_i \leq B_i$. Little R hopes that **no matter** where the test starting point $s$ is chosen, the absolute value of the difference between the numbers of pillars moved over by the two robots is always **less than or equal to** $2$. He wants to know how many height-setting schemes satisfy this requirement. Little R considers two schemes different if and only if there exists some $k$ such that the height of pillar $k$ is different in the two schemes. Please output the number of valid schemes modulo $10^9 + 7$.

The first line contains a positive integer $n$, representing the number of pillars. The next $n$ lines each contain two positive integers $A_i, B_i$, representing the minimum and maximum height of pillar $i$.

Output one line with one integer, the answer modulo $10^9 + 7$.

### More Samples You can get more samples through the additional files. #### Sample 2 See `robot/robot2.in` and `robot/robot2.ans` in the additional files. #### Sample 3 See `robot/robot3.in` and `robot/robot3.ans` in the additional files. #### Sample 4 See `robot/robot4.in` and `robot/robot4.ans` in the additional files. ### Explanation for Sample 1 There are two possible pillar height settings: - Heights: `3 2 3 2 3`. If the starting point is set to $5$, the `P`-type robot will stop at pillar $1$, moving across $4$ pillars. The `Q`-type robot stops at pillar $5$, moving across $0$ pillars. This does not satisfy the condition. - Heights: `3 2 4 2 3`. In this case, no matter where the starting point is chosen, the condition is satisfied. Details are shown in the table below: ::cute-table{tuack} | Starting index | P-type robot | Q-type robot | | :----------: | :----------: | :----------: | | $1$ | Stops at pillar $1$, moves across $0$ | Stops at pillar $2$, moves across $1$ | | $2$ | Stops at pillar $2$, moves across $0$ | Stops at pillar $2$, moves across $0$ | | $3$ | Stops at pillar $1$, moves across $2$ | Stops at pillar $5$, moves across $2$ | | $4$ | Stops at pillar $4$, moves across $0$ | Stops at pillar $4$, moves across $0$ | | $5$ | Stops at pillar $4$, moves across $1$ | Stops at pillar $5$, moves across $0$ | ### Constraints For all testdata: $1 \leq n \leq 300$, $1 \leq A_i \leq B_i \leq 10^9$. The detailed limits for each test point are shown in the table below: ::cute-table{tuack} | Test point ID | $n\le$ | Special property | | :----------: | :----------: | :----------: | | $1,2$ | $7$ | $A_i=B_i,B_i\le 7$ | | $3,4$ | $7$ | $B_i\le 7$ | | $5,6,7$ | $50$ | $B_i\le 100$ | | $8,9,10$ | $300$ | $B_i\le 10^4$ | | $11,12$ | $50$ | $A_i=1,B_i=10^9$ | | $13,14,15$ | $50$ | None. | | $16,17$ | $150$ | ^ | | $18,19$ | $200$ | ^ | | $20$ | $300$ | ^ | Translated by ChatGPT 5