Nested Loop Iteration Count

Mirko wrote a function with N nested loops. Each loop is written in the following form:

for (v = X_i; v ≤ Y_i; ++v)

Here, each X_i and Y_i is either a positive integer (at most \(10^5\)) or one of the previously declared loop variables (denoted by lowercase letters). It is guaranteed that for each loop, at least one of X_i and Y_i is an integer constant.

The function computes the total number of iterations executed by these nested loops and returns the answer modulo \(10^9+7\). Formally, if the loops iterate over variables \(v_1, v_2, \dots, v_N\) with the constraint \[ v_i \in \Bigl[\,\begin{cases} L_i, & \text{if } X_i \text{ is an integer} \\ \text{(value of the variable denoted by }X_i\text{)}, & \text{if } X_i \text{ is a letter}\end{cases}, \quad \begin{cases} R_i, & \text{if } Y_i \text{ is an integer} \\ \text{(value of the variable denoted by }Y_i\text{)}, & \text{if } Y_i \text{ is a letter}\end{cases}\Bigr] \] then the function returns \[ \left( \sum_{v_1, v_2, \dots, v_N} 1 \right) \bmod (10^9+7). \]

inputFormat

The first line contains a single integer N representing the number of loops.

Each of the next N lines contains two tokens Xi and Yi. Each token is either a positive integer (at most \(10^5\)) or a lowercase letter. If a token is a letter, it always refers to one of the previously declared loop variables.

outputFormat

Output a single integer --- the return value of the function, i.e. the total number of iterations of the nested loops modulo \(10^9+7\).

sample

1
1 3

3