Bessie ma dwie tablice długości $N$ ($1\le N\le500$). Element $i$ pierwszej to $a_i$ ($1\le a_i\le10^6$), drugiej $b_i$ ($1\le b_i\le10^6$).

Chce dzielić na niepuste podtablice, tak że:

1. Każdy element należy dokładnie do jednej.
2. Obie mają tę samą liczbę $k$ części.
3. Dla każdego $1\le i\le k$ średnia części $i$ od lewej pierwszej jest mniejsza lub równa odpowiadającej drugiej.

Policz podziały modulo $10^9+7$. Różne, gdy liczba części inna lub element należy do innej części.

Wejście

Pierwszy wiersz $N$.

Następny $a_1,a_2,\ldots,a_N$.

Następny $b_1,b_2,\ldots,b_N$.

Wyjście

Liczba poprawnych podziałów na niepuste podtablice modulo $10^9+7$.

Przykład

Wejście 1

2
1 2
2 2

Wyjście 1

2

Uwagi

Dwa poprawne podziały, pierwsza tablica, potem druga:

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

Wejście 2

3
1 3 2
2 2 2

Wyjście 2

3

Uwagi

Trzy poprawne podziały, pierwsza, potem druga:

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

Wejście 3

5
2 5 1 3 2
2 1 5 2 2

Wyjście 3

1

Uwagi

Jedyny podział, pierwsza, potem druga: $[2],[5,1,3],[2]$ / $[2],[1,5],[2,2]$.

Wejście 4

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

Wyjście 4

140

Podzadania

• Wejścia 5–6: $N\le10$.
• Wejścia 7–9: $N\le80$.
• Wejścia 10–17: $N\le300$.
• Wejścia 18–20: $N\le500$.

Autor zadania: Alex Liang