CF37D.Lesson Timetable

When Petya has free from computer games time, he attends university classes. Every day the lessons on Petya’s faculty consist of two double classes. The floor where the lessons take place is a long corridor with M classrooms numbered from 1 to M, situated along it.

All the students of Petya’s year are divided into N groups. Petya has noticed recently that these groups’ timetable has the following peculiarity: the number of the classroom where the first lesson of a group takes place does not exceed the number of the classroom where the second lesson of this group takes place.

Once Petya decided to count the number of ways in which one can make a lesson timetable for all these groups. The timetable is a set of 2_N_ numbers: for each group the number of the rooms where the first and the second lessons take place. Unfortunately, he quickly lost the track of his calculations and decided to count only the timetables that satisfy the following conditions:

1. On the first lesson in classroom i exactly X__i groups must be present.

2. In classroom i no more than Y__i groups may be placed.

Help Petya count the number of timetables satisfying all those conditionsю As there can be a lot of such timetables, output modulo 109 + 7.

当佩佳不玩电脑游戏时，他会去上大学的课程。每天佩佳所在院系的课程由两节连上的大课（即“双课”）组成。上课所在的楼层是一条长长的走廊，沿走廊分布着编号为 $1$ 到 $M$ 的 $M$ 间教室。

佩佳所在年级的所有学生被分为 $N$ 个小组。佩佳最近注意到，这些小组的课表具有如下特点：每个小组第一节课所在的教室编号不大于该小组第二节课所在的教室编号。

某天佩佳决定计算出为所有这些小组安排课表的方案总数。一份课表由 $2N$ 个数字构成：对每个小组，分别指定其第一节课和第二节课所在的教室编号。但佩佳很快就在计算中迷失了方向，于是他决定只统计满足以下条件的课表数量：

1. 在第 $i$ 间教室上第一节课的小组恰好有 $X_i$ 个；
2. 第 $i$ 间教室最多可安排 $Y_i$ 个小组（即在该教室上第一节课或第二节课的小组总数不超过 $Y_i$）。

请帮助佩佳计算满足上述所有条件的课表数量。由于方案数可能很大，请将结果对 $10^9 + 7$ 取模后输出。

The first line contains one integer M (1 ≤ M ≤ 100) — the number of classrooms.

The second line contains M space-separated integers — X__i (0 ≤ X__i ≤ 100) the amount of groups present in classroom i during the first lesson.

The third line contains M space-separated integers — Y__i (0 ≤ Y__i ≤ 100) the maximal amount of groups that can be present in classroom i at the same time.

It is guaranteed that all the X__i ≤ Y__i, and that the sum of all the X__i is positive and does not exceed 1000.

第一行包含一个整数 $M$（$1 \leq M \leq 100$）—— 教室的数量。

第二行包含 $M$ 个用空格分隔的整数 —— $X_i$（$0 \leq X_i \leq 100$），表示第 $i$ 间教室在第一节课时存在的小组数量。

第三行包含 $M$ 个用空格分隔的整数 —— $Y_i$（$0 \leq Y_i \leq 100$），表示第 $i$ 间教室在同一时刻最多可容纳的小组数量。

保证对所有 $i$ 都有 $X_i \leq Y_i$，且所有 $X_i$ 的总和为正数且不超过 $1000$。

In the single line output the answer to the problem modulo 109 + 7.

在单行中输出该问题的答案对 $10^9 + 7$ 取模的结果。

In the second sample test the first and the second lessons of each group must take place in the same classroom, that’s why the timetables will only be different in the rearrangement of the classrooms’ numbers for each group, e.g. 3! = 6.

在第二个样例测试中，每组的第一节课和第二节课必须在同一间教室进行，因此课表的差异仅在于每组教室编号的排列方式，例如 $3! = 6$。