У Беси есть два массива длины \(N\) (\(1 \le N \le 500\)). \(i\)-ый элемент
первого массива есть \(a_i\) (\(1 \le a_i \le 10^6\)). \(i\)-ый элемент
второго массива есть \(b_i\) (\(1 \le b_i \le 10^6\)).
Беси хочет разделить два массива на не-пустые подмассивы так
что будут выполняться следующие условия:
- Каждый элемент принадлежит точно 1 подмассиву.
- Оба массива разделены на одинаковое количество подмассивов - пусть \(k\).
То есть, первый массив разделён ровно на \(k\) подмассивов.
И второй массив также разделён ровно на \(k\) подмассивов.
- Для всех \(1 \le i \le k\),, среднее \(i\)-го подмассива слева первого массива
строго меньше либо равно среднему \(i\)-го
подмассива слева второго массива.
Подсчитайте сколькими способами можно разделить массивы на непустые подмассивы
выполнив указанные ограничения. Выводить ответ по модулю \(10^9+7\).
Два способа считаются различными, если количество элементов подмассива
различается или некоторый элемент принадлежит различным подмассивам.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\).
Следующая строка содержит \(a_1,a_2,...,a_N\).
Следующая строка содержит \(b_1,b_2,...,b_N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите количество способов разделить два массива на непустые подмассивы
удовлетворяющих вышеописанным условиям. Ответ выводите по модулю \(10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
2 2
|
2
|