Bessie hat zwei Arrays der Länge $N$ ($1\le N\le500$). Element $i$ im ersten ist $a_i$ ($1\le a_i\le10^6$), im zweiten $b_i$ ($1\le b_i\le10^6$).

Beide sollen in nichtleere Teilarrays zerlegt werden, sodass:

1. Jedes Element genau zu einem gehört.
2. Beide die gleiche Zahl $k$ von Teilen haben.
3. Für jedes $1\le i\le k$ der Mittelwert des $i$-ten Teils von links im ersten kleiner oder gleich dem im zweiten ist.

Zähle Zerlegungen modulo $10^9+7$. Verschieden sind sie bei anderer Teilzahl oder wenn ein Element zu einem anderen Teil gehört.

Eingabe

Erste Zeile $N$.

Nächste $a_1,a_2,\ldots,a_N$.

Nächste $b_1,b_2,\ldots,b_N$.

Ausgabe

Zahl gültiger Zerlegungen in nichtleere Teilarrays modulo $10^9+7$.

Beispiele

Eingabe 1

2
1 2
2 2

Ausgabe 1

2

Hinweis

Zwei gültige Zerlegungen, erstes Array dann zweites:

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

Eingabe 2

3
1 3 2
2 2 2

Ausgabe 2

3

Hinweis

Drei gültige Zerlegungen, erstes dann zweites:

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

Eingabe 3

5
2 5 1 3 2
2 1 5 2 2

Ausgabe 3

1

Hinweis

Einzige Zerlegung, erstes dann zweites: $[2],[5,1,3],[2]$ / $[2],[1,5],[2,2]$.

Eingabe 4

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

Ausgabe 4

140

Teilaufgaben

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

Aufgabenautor: Alex Liang