$N$ bobrów i $N$ revaebów zmierzy się ze sobą w nadchodzących zawodach programistycznych! Zawody składają się z $N$ zadań, przy czym $k$-te zadanie ma całkowitą liczbę punktów $p_k$ z przedziału od $l_k$ do $r_k$ włącznie. Wynik uczestnika to suma punktów za rozwiązane przez niego zadania.

W dniu zawodów wiadomo, że $i$-ty bóbr rozwiązał pierwsze $i$ zadań, a $j$-ty revaeb rozwiązał ostatnie $j$ zadań. Dodatkowo, jedyną parą uczestników o takim samym wyniku są ci, którzy rozwiązali wszystkie zadania, czyli $N$-ty bóbr i $N$-ty revaeb. Mając te informacje, oblicz liczbę możliwych przypisań wartości punktowych do zadań w zawodach. Ponieważ liczba ta może być duża, wyprowadź jej resztę z dzielenia przez $10^9 + 7$.

Wejście

W pierwszej linii znajduje się $N$ ($1 \leq N \leq 50$), liczba zadań w zawodach.

Następnie następuje $N$ linii. $k$-ta z tych linii zawiera dwie liczby całkowite oddzielone spacją, $l_k$ oraz $r_k$ ($1 \le l_k \le r_k \le 2000$).

Wyjście

Wyprowadź jedną linię zawierającą odpowiedź: liczbę ciągów wartości punktowych modulo $10^9+7$.

Scoring

• ($10$ punktów) $N \leq 8$ oraz $r_k \leq 8$ dla wszystkich $k$.
• ($30$ punktów) $l_k = 1$ dla wszystkich $k$ oraz istnieje stałe $R$ takie, że $r_k = R$ dla wszystkich $k$.
• ($30$ punktów) $r_k \leq 100$ dla wszystkich $k$.
• ($30$ punktów) Brak dodatkowych ograniczeń.

Przykład

Przykład 1

4
1 1
2 2
3 3
10 10

Wyjście 1

1

Przykład 2

1
1 2000

Wyjście 2

2000

Przykład 3

4
1 2
1 2
1 2
1 2

Wyjście 3

2

Przykład 4

5
1 3
2 4
1 4
1 2
3 3

Wyjście 4

18

Przykład 5

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

Wyjście 5

5120

Note

Wyjaśnienie przykładu 1

Wartości punktowe zadań mogą wynosić tylko $1, 2, 3, 10$. Przy użyciu tych wartości punktowych wyniki bobrów wynoszą odpowiednio $1, 3, 6, 16$, a wyniki revaebów odpowiednio $10, 13, 15, 16$. Wszystkie te wyniki są różne, poza wynikiem $16$ uzyskanym przez $4$-tego bobra i $4$-tego revaeba, więc ten jeden ciąg jest poprawny, co daje odpowiedź $1$.

Wyjaśnienie przykładu 2

Ten przykład spełnia ograniczenia dla drugiego podzadania.

Wyjaśnienie przykładu 3

Ten przykład spełnia ograniczenia dla drugiego podzadania.

Jedynymi poprawnymi ciągami wartości punktowych są $1, 2, 2, 2$ oraz $2, 2, 2, 1$, co daje odpowiedź $2$.

Wyjaśnienie przykładu 5

Ten przykład spełnia ograniczenia dla drugiego podzadania.