Vòng lặp

Xét một hàm code được viết theo dạng sau:

int code() {
    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;
}

Có tổng cộng \(N\) vòng lặp lồng nhau.
Vòng lặp thứ \(i\) chạy từ \(X_i\) đến \(Y_i\), trong đó mỗi \(X_i\) hoặc \(Y_i\) có thể:

• là một số nguyên dương không vượt quá \(100000\), hoặc
• là tên của một biến thuộc vòng lặp ngoài (ví dụ: a, b, …).

Mỗi vòng lặp đều có ít nhất một trong hai giá trị \(X_i\) hoặc \(Y_i\) là số nguyên (không phải tên biến).
Các biến vòng lặp được đặt tên lần lượt theo bảng chữ cái: vòng 1 là a, vòng 2 là b, ..., vòng \(N\) là chữ cái thứ \(N\).

Yêu cầu của bài toán là tính tổng số lần câu lệnh ret = (ret + 1) % MOD được thực thi.

Kết quả phải được lấy modulo \(10^9 + 7\).

\InputFile

• Dòng đầu chứa số nguyên \(N \ (1 \le N \le 26)\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(X_i\) và \(Y_i\), được phân tách bởi dấu cách.
  Mỗi giá trị có thể là một số nguyên dương \(\le 100000\) hoặc là tên biến
  a, b, ..., tương ứng với các vòng ngoài.
  Nếu cả hai đều là số, đảm bảo \(X_i \le Y_i\).

\OutputFile
In ra một số nguyên --- giá trị trả về của hàm.

\Scoring

• Subtask 1 (15 điểm): \(n \le 5\) và mọi \(X_i, Y_i\) (nếu là số) có giá trị không quá \(30\).
• Subtask 2 (15 điểm): Mọi \(X_i\) và \(Y_i\) đều là số.
• Subtask 3 (20 điểm): \(X_1 = X_2 = \dots = X_n = 1\)
  và với mọi \(i > 1\), \(Y_i\) là chữ cái thứ \(i-1\) trong bảng chữ cái tiếng Anh
  (nói cách khác, \(Y_2 = \texttt{a}\), \(Y_3 = \texttt{b}\), \(Y_4 = \texttt{c}\), …).
• Subtask 4 (20 điểm): Với mọi \(i > 1\), \(Y_i\) là chữ cái.
• Subtask 5 (30 điểm): Không có ràng buộc gì thêm.

\Examples

\beginexample
\exmp
2
1 2
a 3

5

\exmp
3
2 3
1 2
1 a

10

\exmp
3
1 2
a 3
1 b

11

\endexample