У Фермера Джона есть N коров (1 ≤ N ≤ 20) с высотами a
1…a
N. Его амбар имеет N стойл с максимальными высотами b
1…b
N (поэтому например, b
5=17 означает, что коров с высотой не более 17 можно разместить в стойле 5). Сколькими различными способами ФД может разместить коров по стойлам, так чтобы ограничение по высоте было выполнено для каждого стойла.
Входные данные
Первая строка содержит N. Вторая строка содержит N разделённых одиночными пробелами чисел a
1, a
2,…,a
N. Третья строка содержит N разделённых одиночными пробелами чисел b
1,b
2,…,b
N. Все величины - целые числа в интервале [1,10
9].
Выходные данные
Количество способов, которыми ФД может разместить коров в стойлах, так чтобы для каждого стойла был удовлетворён лимит по высоте. Заметьте, что ответ может быть очень большим, поэтому для него требуется использовать 64-битную целую переменную, такую как "long long" в C++.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
4
1 2 3 4
2 4 3 4
|
8 |
В этом примере мы не можем разместить третью корову в первое стойло, поскольку 3=a3>b1=2. Аналогично, мы не можем разместить 4-ую корову в 1-ое или 3 -е стойло. Один из 8 способов размещения: корову 1 в стойло 1, корову 2 в стойло 2, корову 3 в стойло 3 корову 4 в стойло 4. |