Bessie ha due array lunghi $N$ ($1\le N\le500$). L’elemento $i$ del primo è $a_i$ ($1\le a_i\le10^6$), del secondo $b_i$ ($1\le b_i\le10^6$).

Vuole dividerli in sottoarray non vuoti tali che:

1. Ogni elemento appartenga esattamente a uno.
2. Entrambi abbiano lo stesso numero $k$ di parti.
3. Per ogni $1\le i\le k$, la media della parte $i$ da sinistra del primo sia minore o uguale alla corrispondente del secondo.

Conta le divisioni modulo $10^9+7$. Sono diverse se cambia il numero di parti o qualche elemento appartiene a un’altra parte.

Input

Prima riga $N$.

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

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

Output

Numero di divisioni valide in sottoarray non vuoti modulo $10^9+7$.

Esempi

Input 1

2
1 2
2 2

Output 1

2

Note

Due divisioni valide, prima il primo array poi il secondo:

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

Input 2

3
1 3 2
2 2 2

Output 2

3

Note

Tre divisioni valide, primo e secondo rispettivamente:

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

Input 3

5
2 5 1 3 2
2 1 5 2 2

Output 3

1

Note

Unica divisione, primo e secondo rispettivamente: $[2],[5,1,3],[2]$ / $[2],[1,5],[2,2]$.

Input 4

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

Output 4

140

Sottoproblemi

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

Autore del problema: Alex Liang