В свободное от компьютерных игр время Петя ходит в университет на занятия. Каждый день занятия на факультете у Пети состоят из двух пар. Этаж на котором проходят занятия у Пети, представляет из себя длинный коридор, вдоль которого расположены M аудиторий, пронумерованных от 1 до M.
Поток, на котором учится Петя, разбит на N групп. Недавно, Петя заметил, что расписание занятий у этих групп обладает следующей особенностью: номер аудитории, в которой проходит первое занятие у какой-то группы не превосходит номера аудитории для второго занятия этой группы.
Как-то раз, Петя решил посчитать, сколькими способами можно составить расписание занятий для всех групп. Расписание — это набор из 2N чисел: для каждой группы номер аудитории для первого занятия, и номер аудитории для второго занятия. К сожалению, он быстро сбился со счета, и решил, считать только расписания, удовлетворяющие следующим условиям:
1) На первом занятии в i-ой аудитории должно находиться ровно Xi групп.
2) В i-ой аудитории может поместиться не более чем Yi групп.
Помогите Пете посчитать количество расписаний удовлетворяющих всем этим условиям. Так как и таких расписаний может быть много, выведите ответ по модулю 109 + 7.
Примечание
Во втором тесте из примера первое и второе занятия у каждой группы должны проходить в одной и той же аудитории, поэтому расписания будут отличаться только перестановкой номеров этих аудиторий для каждой группы, то есть 3! = 6.