Dans les concours de programmation, les castors résolvent les problèmes dans l'ordre, du premier au dernier. Les revaebs, en revanche, sont un type spécial de rongeur qui résout les problèmes dans l'ordre inverse, du dernier au premier.

$N$ castors et $N$ revaebs vont s'affronter lors du prochain concours de programmation ! Le concours se compose de $N$ problèmes, le $k^{\text{ième}}$ problème ayant une valeur en points entière $p_k$ comprise entre $l_k$ et $r_k$ inclus. Le score d'un participant est la somme des valeurs en points des problèmes qu'il a résolus.

Le jour du concours, on sait que le $i^{\text{ième}}$ castor a résolu les $i$ premiers problèmes, et que le $j^{\text{ième}}$ revaeb a résolu les $j$ derniers problèmes. De plus, la seule paire de participants ayant le même score est celle des deux participants ayant résolu tous les problèmes, c'est-à-dire le $N^{\text{ième}}$ castor et le $N^{\text{ième}}$ revaeb. Étant donné ces informations, comptez le nombre d'assignations possibles de valeurs en points aux problèmes du concours. Comme ce nombre peut être grand, donnez son reste modulo $10^9 + 7$.

Entrée

La première ligne contient $N$ ($1 \leq N \leq 50$), le nombre de problèmes du concours.

$N$ lignes suivent. La $k^{\text{ième}}$ de ces lignes contient deux entiers séparés par un espace, $l_k$ et $r_k$ ($1 \le l_k \le r_k \le 2000$).

Sortie

Affichez une ligne contenant la réponse : le nombre de séquences de valeurs en points modulo $10^9+7$.

Barème

• ($10$ points) $N \leq 8$ et $r_k \leq 8$ pour tout $k$.
• ($30$ points) $l_k = 1$ pour tout $k$ et il existe un $R$ fixe tel que $r_k = R$ pour tout $k$.
• ($30$ points) $r_k \leq 100$ pour tout $k$.
• ($30$ points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

4
1 1
2 2
3 3
10 10

Sortie 1

1

Entrée 2

1
1 2000

Sortie 2

2000

Entrée 3

4
1 2
1 2
1 2
1 2

Sortie 3

2

Entrée 4

5
1 3
2 4
1 4
1 2
3 3

Sortie 4

18

Entrée 5

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

Sortie 5

5120

Remarque

Explication de l'exemple 1

Les valeurs en points des problèmes ne peuvent être que $1, 2, 3, 10$. En utilisant ces valeurs, les scores des castors sont respectivement $1, 3, 6, 16$ et les scores des revaebs sont respectivement $10, 13, 15, 16$. Tous ces scores sont différents, à l'exception du score de $16$ obtenu par le $4^{\text{ième}}$ castor et le $4^{\text{ième}}$ revaeb, donc cette séquence est valide, ce qui donne $1$ comme réponse.

Explication de l'exemple 2

Cet exemple satisfait les contraintes de la deuxième sous-tâche.

Explication de l'exemple 3

Cet exemple satisfait les contraintes de la deuxième sous-tâche.

Les seules séquences valides de valeurs en points sont $1, 2, 2, 2$ et $2, 2, 2, 1$, ce qui donne $2$ comme réponse.

Explication de l'exemple 5

Cet exemple satisfait les contraintes de la deuxième sous-tâche.