Bessie a deux tableaux de longueur $N$ ($1\le N\le500$). Le $i$-ème du premier est $a_i$ ($1\le a_i\le10^6$), du second $b_i$ ($1\le b_i\le10^6$).

Elle veut les diviser en sous-tableaux non vides tels que :

1. Chaque élément appartient à exactement un sous-tableau.
2. Les deux ont le même nombre $k$ de sous-tableaux.
3. Pour tout $1\le i\le k$, la moyenne du $i$-ème depuis la gauche dans le premier est inférieure ou égale à celle du second.

Comptez les découpages modulo $10^9+7$. Ils diffèrent si le nombre de parties change ou si un élément appartient à une autre partie.

Entrée

Première ligne $N$.

Suivante $a_1,a_2,\ldots,a_N$.

Suivante $b_1,b_2,\ldots,b_N$.

Sortie

Nombre de découpages valides en sous-tableaux non vides modulo $10^9+7$.

Exemples

Entrée 1

2
1 2
2 2

Sortie 1

2

Remarque

Deux découpages valides, premier tableau puis second :

1. $[1],[2]$ / $[2],[2]$.
2. $[1,2]$ / $[2,2]$.

Entrée 2

3
1 3 2
2 2 2

Sortie 2

3

Remarque

Trois découpages valides, premier puis second :

1. $[1,3],[2]$ / $[2,2],[2]$.
2. $[1,3],[2]$ / $[2],[2,2]$.
3. $[1,3,2]$ / $[2,2,2]$.

Entrée 3

5
2 5 1 3 2
2 1 5 2 2

Sortie 3

1

Remarque

Unique découpage, premier puis second : $[2],[5,1,3],[2]$ / $[2],[1,5],[2,2]$.

Entrée 4

7
3 5 2 3 4 4 1
5 3 5 3 3 4 1

Sortie 4

140

Sous-tâches

• Entrées 5–6 : $N\le10$.
• Entrées 7–9 : $N\le80$.
• Entrées 10–17 : $N\le300$.
• Entrées 18–20 : $N\le500$.

Auteur du problème : Alex Liang