Bessie tiene dos arreglos de longitud $N$ ($1\le N\le500$). El elemento $i$ del primero es $a_i$ ($1\le a_i\le10^6$), del segundo $b_i$ ($1\le b_i\le10^6$).

Quiere dividirlos en subarreglos no vacíos de forma que:

1. Cada elemento pertenezca a exactamente uno.
2. Ambos tengan el mismo número $k$ de partes.
3. Para todo $1\le i\le k$, el promedio de la parte $i$ desde la izquierda del primero sea menor o igual al correspondiente del segundo.

Cuenta las divisiones módulo $10^9+7$. Son diferentes si cambia el número de partes o algún elemento pertenece a otra parte.

Entrada

Primera línea $N$.

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

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

Salida

Número de divisiones válidas en partes no vacías módulo $10^9+7$.

Ejemplos

Entrada 1

2
1 2
2 2

Salida 1

2

Nota

Dos divisiones válidas, primero el primer arreglo y luego el segundo:

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

Entrada 2

3
1 3 2
2 2 2

Salida 2

3

Nota

Tres divisiones válidas, primero y 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

Salida 3

1

Nota

Única división, primero y 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

Salida 4

140

Subtareas

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

Autor del problema: Alex Liang