(99 баллов) В университете Инфаполис учится N групп студентов, для обучения которых используется N аудиторий. Известно количество студентов в каждой группе и количество мест в каждой аудитории. Группа всегда занимает целую аудиторию (группы не объединяются). Администрацию университета заинтересовал вопрос: сколько существует способов рассадить все группы по аудиториям, и сколько групп (по одной) вмещаются в самую маленькую аудиторию.
Входные данные представлены в файле 26-84.txt следующим образом. В первой строке записано натуральное число N (1 ≤ N ≤ 100 000) -- количество аудиторий (и количество групп). В следующей строке записано N натуральных чисел -- количество студентов в каждой группе (целые числа, не превышающие 1 000 000). В третьей строке записано N натуральных чисел -- количество мест в каждой аудитории (целые числа, не превышающие 1 000 000).
Запишите в ответе два числа: сначала количество способов рассадить всех по аудиториям по модулю 100000007 (то есть, остаток от деления искомого числа на 100000007), затем количество групп, каждая из которых помещается в самую маленькую аудиторию.
Пример входного файла:
3
2 3 4
5 6 3
При таких исходных данных всего есть 4 варианта размещения (A5: 2 означает, что в аудитории вместимостью 5 человек размещается группа из 2-х человек):
1) A5: 2, A6: 4, A3: 3,
2) A5: 4, A6: 2, A3: 3,
3) A5: 4, A6: 3, A3: 2,
4) A5: 3, A6: 4, A3: 2.
В самой маленькой аудитории (на 5 человек) можно разместить одну из двух 2 групп (из 2-х или 3-х человек). Ответ: 4 2.