Bessie tem dois vetores de comprimento $N$ ($1\le N\le500$). O elemento $i$ do primeiro é $a_i$ ($1\le a_i\le10^6$), do segundo $b_i$ ($1\le b_i\le10^6$).

Quer dividi-los em subvetores não vazios tais que:

1. Cada elemento pertença a exatamente um.
2. Ambos tenham o mesmo número $k$ de partes.
3. Para todo $1\le i\le k$, a média da parte $i$ da esquerda do primeiro seja menor ou igual à correspondente do segundo.

Conte as divisões módulo $10^9+7$. Diferem se muda o número de partes ou se algum elemento pertence a outra parte.

Entrada

Primeira linha $N$.

Próxima $a_1,a_2,\ldots,a_N$.

Próxima $b_1,b_2,\ldots,b_N$.

Saída

Número de divisões válidas em subvetores não vazios módulo $10^9+7$.

Exemplos

Entrada 1

2
1 2
2 2

Saída 1

2

Note

Duas divisões válidas, primeiro vetor e depois segundo:

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

Entrada 2

3
1 3 2
2 2 2

Saída 2

3

Note

Três divisões válidas, primeiro e segundo respectivamente:

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

Entrada 3

5
2 5 1 3 2
2 1 5 2 2

Saída 3

1

Note

Única divisão, primeiro e segundo respectivamente: $[2],[5,1,3],[2]$ / $[2],[1,5],[2,2]$.

Entrada 4

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

Saída 4

140

Subtarefas

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

Autor do problema: Alex Liang