D. Расписание занятий
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В свободное от компьютерных игр время Петя ходит в университет на занятия. Каждый день занятия на факультете у Пети состоят из двух пар. Этаж на котором проходят занятия у Пети, представляет из себя длинный коридор, вдоль которого расположены M аудиторий, пронумерованных от 1 до M.

Поток, на котором учится Петя, разбит на N групп. Недавно, Петя заметил, что расписание занятий у этих групп обладает следующей особенностью: номер аудитории, в которой проходит первое занятие у какой-то группы не превосходит номера аудитории для второго занятия этой группы.

Как-то раз, Петя решил посчитать, сколькими способами можно составить расписание занятий для всех групп. Расписание — это набор из 2N чисел: для каждой группы номер аудитории для первого занятия, и номер аудитории для второго занятия. К сожалению, он быстро сбился со счета, и решил, считать только расписания, удовлетворяющие следующим условиям:

1) На первом занятии в i-ой аудитории должно находиться ровно Xi групп.

2) В i-ой аудитории может поместиться не более чем Yi групп.

Помогите Пете посчитать количество расписаний удовлетворяющих всем этим условиям. Так как и таких расписаний может быть много, выведите ответ по модулю 109 + 7.

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

В первой строке записано одно целое число M (1 ≤ M ≤ 100) — количество аудиторий.

Во второй строке, через пробел, записаны M целых чисел — Xi (0 ≤ Xi ≤ 100) количество групп, находящихся в i-ой аудитории во время первого занятия.

Во третьей строке, через пробел, записаны M целых чисел — Yi (0 ≤ Yi ≤ 100) максимальное количество групп, которые могут одновременно находится в i - ой аудитории.

Гарантируется, что все Xi ≤ Yi, и что сумма всех Xi положительна и не превосходит 1000.

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

В единственной строке выведите ответ на задачу по модулю 109 + 7.

Примеры
Входные данные
3
1 1 1
1 2 3
Выходные данные
36
Входные данные
3
1 1 1
1 1 1
Выходные данные
6
Примечание

Во втором тесте из примера первое и второе занятия у каждой группы должны проходить в одной и той же аудитории, поэтому расписания будут отличаться только перестановкой номеров этих аудиторий для каждой группы, то есть 3! = 6.