На соревнованиях по программированию бобры решают задачи по порядку, от первой до последней. Реваэбы (revaebs), напротив, — это особый вид грызунов, которые решают задачи в обратном порядке, от последней до первой.

$N$ бобров и $N$ реваэбов будут соревноваться друг с другом в предстоящем соревновании по программированию! Соревнование состоит из $N$ задач, при этом $k$-я задача имеет целочисленную стоимость $p_k$ в диапазоне от $l_k$ до $r_k$ включительно. Оценка участника — это сумма стоимостей решенных им задач.

Известно, что в день соревнования $i$-й бобр решил первые $i$ задач, а $j$-й реваэб решил последние $j$ задач. Кроме того, единственная пара участников с одинаковыми оценками — это те двое, которые решили все задачи: $N$-й бобр и $N$-й реваэб. Учитывая эту информацию, подсчитайте количество возможных способов распределения стоимостей задач. Поскольку это число может быть большим, выведите его остаток от деления на $10^9 + 7$.

Входные данные

Первая строка содержит $N$ ($1 \leq N \leq 50$), количество задач в соревновании.

Далее следуют $N$ строк. $k$-я из этих строк содержит два целых числа, разделенных пробелом: $l_k$ и $r_k$ ($1 \le l_k \le r_k \le 2000$).

Выходные данные

Выведите одну строку, содержащую ответ: количество последовательностей стоимостей задач по модулю $10^9+7$.

Подзадачи

• ($10$ баллов) $N \leq 8$ и $r_k \leq 8$ для всех $k$.
• ($30$ баллов) $l_k = 1$ для всех $k$ и существует фиксированное $R$ такое, что $r_k = R$ для всех $k$.
• ($30$ баллов) $r_k \leq 100$ для всех $k$.
• ($30$ баллов) Без дополнительных ограничений.

Примеры

Входные данные 1

4
1 1
2 2
3 3
10 10

Выходные данные 1

1

Входные данные 2

1
1 2000

Выходные данные 2

2000

Входные данные 3

4
1 2
1 2
1 2
1 2

Выходные данные 3

2

Входные данные 4

5
1 3
2 4
1 4
1 2
3 3

Выходные данные 4

18

Входные данные 5

6
1 5
1 5
1 5
1 5
1 5
1 5

Выходные данные 5

5120

Примечание

Пояснение к примеру 1

Стоимости задач могут быть только $1, 2, 3, 10$. При таких стоимостях оценки бобров равны $1, 3, 6, 16$ соответственно, а оценки реваэбов равны $10, 13, 15, 16$ соответственно. Все они различны, за исключением оценки $16$, полученной $4$-м бобром и $4$-м реваэбом, поэтому данная последовательность является допустимой, что дает ответ $1$.

Пояснение к примеру 2

Этот пример удовлетворяет ограничениям второй подзадачи.

Пояснение к примеру 3

Этот пример удовлетворяет ограничениям второй подзадачи.

Единственными допустимыми последовательностями стоимостей задач являются $1, 2, 2, 2$ и $2, 2, 2, 1$, что дает ответ $2$.

Пояснение к примеру 5

Этот пример удовлетворяет ограничениям второй подзадачи.