19653번 - Robot 다국어

There are two robots P and Q and now we are going to run some experiments on them.

There are n pillars on a row numbered from 1 to n and the height of each pillar i is a positive integer h_i. Both robots can move from one to its neighbors, which means if the robot is now at pillar i, it can only try moving to i−1 or i+1.

In each experiment, we will pick a starting pillar s and put two robots on it. Two robots will then move under certain rules:

Robot P will always move to the left, but it can't move to the pillars that are higher than pillar s. Formally, it will stop at pillar l, (l ≤ s) if and only if:

• l = 1 or h_l − 1 > h_s
• h_j ≤ h_s holds for all l ≤ j ≤ s

Robot Q will always move to the right, but it can only move to the pillars that are shorter than pillar s. Formally, it will stop at pillar r, (r ≥ s) if and only if:

• r = n or h_r + 1 ≥ h_s
• h_j < h_s holds for all s < j ≤ r

Now for each pillar i, we can choose its height to be any integer in [A_i, B_i]. We hope that no matter which pillar we choose as the starting pillar s, the absolute difference between P and Q's moving distance (i.e. the number of pillars one robot has gone through) is not larger than 2.

Please calculate the number of plans to choose pillars' height satisfying the above condition. We consider two plans to be different if there exists a pillar k that has different height in those two plans. Since the answer may be large, please output the answer modulo 10⁹+7.

The first line contains an integer n, indicating the number of pillars.

In the following n lines, each line contains two integers A_i, B_i.

Output one integer on one line, the answer modulo 10⁹+7.

For all test cases, 1 ≤ n ≤ 300, 1 ≤ A_i ≤ B_i ≤ 10⁹.