У Bessie два массива длины $N$ ($1\le N\le500$). Элемент $i$ первого — $a_i$ ($1\le a_i\le10^6$), второго — $b_i$ ($1\le b_i\le10^6$).

Разбейте оба на непустые подмассивы так, чтобы:

1. Каждый элемент принадлежит ровно одному.
2. Оба имеют одинаковое число $k$ подмассивов.
3. Для каждого $1\le i\le k$ среднее $i$-го слева подмассива первого не больше среднего соответствующего во втором.

Посчитайте способы по модулю $10^9+7$. Они различны, если число частей различно либо элемент принадлежит другой части.

Входные данные

Первая строка $N$.

Следующая $a_1,a_2,\ldots,a_N$.

Следующая $b_1,b_2,\ldots,b_N$.

Выходные данные

Число допустимых разбиений на непустые подмассивы по модулю $10^9+7$.

Примеры

Входные данные 1

2
1 2
2 2

Выходные данные 1

2

Примечание

Два допустимых способа, сначала первый массив, затем второй:

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

Входные данные 2

3
1 3 2
2 2 2

Выходные данные 2

3

Примечание

Три допустимых способа, сначала первый, затем второй:

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

Входные данные 3

5
2 5 1 3 2
2 1 5 2 2

Выходные данные 3

1

Примечание

Единственный способ, сначала первый, затем второй: $[2],[5,1,3],[2]$ / $[2],[1,5],[2,2]$.

Входные данные 4

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

Выходные данные 4

140

Подзадачи

• Входы 5–6: $N\le10$.
• Входы 7–9: $N\le80$.
• Входы 10–17: $N\le300$.
• Входы 18–20: $N\le500$.

Автор задачи: Alex Liang