#1843. [NOI 2019] Robots

[NOI 2019] Robots

Description

Recently, Bob invented 22 kinds of robots: type P and type Q. Now he wants to test the mobility of these two robots.

There are nn pillars arranged in a row, numbered from 11 to nn. The ii-th pillar has a height of hih_i. The robots can only move between adjacent pillars, that is, if the robot is currently on the ii-th pillar. it can only move to the (i1)(i-1)-th or (i+1)(i+1)-th pillar.

In each test, Bob will choose a number s(1sn)s\,(1 \leq s \leq n), and put the robots on the ss-th pillar. Then the robots will move according to their own rules.

Robots of type P will always move to the left, but it can't move to the pillars that are higher than pillar ss. Formally, it will stop at pllar l(ls)l\,(l \leq s) if and only if:

  • l=1l = 1 or hl1>hsh_{l-1} > h_s
  • hjhsh_j \leq h_s holds for all ljsl \leq j \leq s

Robots of type Q will always move to the right, but it can only move to the pillars that are shorter than pillar ss. Formally, it will stop at pllar r(rs)r\,(r \leq s) if and only if:

  • r=nr = n or hr+1hsh_{r+1} \geq h_s
  • hj<hsh_j < h_s holds for all s<jrs < j \leq r

Bob can set the height of all the pillars, the height of the ii-th pillar can be any integer in range [Ai,Bi][A_i, B_i]. He wants to know how many possible ways are there to set the heights so that no matter which number ss is, the difference between the number of pillars that the robots pass by is not greater than 22.

Since the answer could be very large, you should print the answer module 109+710^9 + 7 instead.

Input

The first line contains a single integer nn.

Each of the next nn lines contains twp integers Ai,BiA_i, B_i.

Output

Print a single integer — the answer module 109+710^9 + 7.

Sample

5
3 3
2 2
3 4
2 2
3 3
1

There are two possible ways to set the heights:

  • If the heights are 323233\,2\,3\,2\,3 respectively. When s=5s = 5, we can see that Robot of type P will stop at pillar 11 (pass by 44 pillars in total) and robot of type Q will stop at pillar 55 (pass by 00 pillars in total), which breaks the condition.
  • If the heights are 324233\,2\,4\,2\,3 respectively. We can show that no matter which number ss is, the condition is always satisfied.

Limits And Hints

For all of the tests, 1n3001 \leq n \leq 300, 1AiBi1091 \leq A_i \leq B_i \leq 10^9.

For partial scores, you can look up at the origin statement (NOI/2019/Day1.pdf).