Robot Movement Balance

Little R is fascinated by robots. Recently he has designed two types of robots, P-type and Q-type. To test their mobility, he arranges n pillars in a row (numbered from 1 to n from left to right), where the height of pillar i is a positive integer h_i.

The two robots are placed on a chosen starting pillar s and move in opposite directions with restrictions:

• P‑robot always moves to the left. It cannot move onto any pillar whose height is greater than h_s (the height at the starting pillar). More precisely, if P‑robot stops at pillar l (l ≤ s), then it holds if and only if both conditions are satisfied:
  1. l = 1 or h_l-1 > h_s.
  2. For each pillar j with l ≤ j ≤ s we have h_j ≤ h_s.
• Q‑robot always moves to the right. It can only move onto pillars whose heights are lower than h_s. More precisely, if Q‑robot stops at pillar r (r ≥ s), then it holds if and only if both conditions are satisfied:
  1. r = n or h_r+1 ≥ h_s.
  2. For each pillar j with s < j ≤ r we have h_j < h_s.

Define for any starting position s:

• Let L be the number of steps the P‑robot takes to the left, i.e. if it stops at pillar l then L = s - l (since it visits pillars l, l+1, ..., s).
• Let R be the number of steps the Q‑robot takes to the right, i.e. if it stops at pillar r then R = r - s (since it visits pillars s, s+1, ..., r).

The requirement is that no matter which pillar is chosen as the start (s can be any from 1 to n), the absolute difference between the numbers of pillars traversed by the two robots (which is |(L+1) - (R+1)| = |L - R|) is at most 2. In other words, for every s the following must hold:

[ |R - L| \le 2. ]

Additionally, Little R can set the height of pillar i arbitrarily within a given range \([A_i, B_i]\) (i.e. \(A_i \le h_i \le B_i\)). Two settings are considered different if there exists an index \(k\) such that the height of the \(k\)th pillar is different in the two settings.

Your task is to calculate the number of settings for the pillar heights that satisfy the above requirement, modulo \(10^9+7\).

inputFormat

The first line contains a single integer n (\(1 \le n \le 10\)), representing the number of pillars.

Then follow n lines. The i-th line contains two integers \(A_i\) and \(B_i\) (\(1 \le A_i \le B_i \le 10^9\)), which represent the minimum and maximum height for the i-th pillar.

outputFormat

Output a single integer, the number of valid settings of pillar heights modulo \(10^9+7\).

sample

1
1 3

3