Description

Mirko wrote the following function:

(C++)

int fun() {
    int ret = 0;
    for (int a = X1; a <= Y1; ++a)
         for (int b = X2; b <= Y2; ++b)
             ...
                 for (int <N-th> = XN; <N-th> <= YN; ++<N-th>)
                     ret = (ret + 1) % 1000000007;
    return ret;
}

(Pascal)

function fun: longint;
var
  ret: longint;
  a, b, ... , y, z: longint;
begin
  ret := 0;
  for a := X1 to Y1 do
    for b := X2 to Y2 do
      ...
        for <N-th> := XN to YN do
          ret := (ret + 1) mod 1000000007;
  fun := ret;
end;

denotes the $N$-th lowercase letter. Each $X_i$ and $Y_i$ may represent the variable name of an outer loop, or a positive integer $\le 10^5$. For example, $X_3$ can be $a$, $b$, or an integer constant. At least one of $X_i$ and $Y_i$ is an integer constant.

Compute the return value of this function.

Input Format

The first line contains a positive integer $N$.

The next $N$ lines each contain $X_i, Y_i$ separated by spaces on the $i$-th line. If both $X_i$ and $Y_i$ are integer constants, then $X_i \le Y_i$.

Output Format

Output one integer in a single line, which is the return value of the function.

2
1 2
a 3

5

3
2 3
1 2
1 a

10

3
1 2
a 3
1 b

11

Hint

Constraints

For $100\%$ of the testdata, $1 \le N \le 26$.

Notes

The score setting of this problem follows the original COCI problem, with a full score of $150$.

Translated from COCI2011-2012 CONTEST #2 T5 FUNKCIJA.

Translated by ChatGPT 5