← 返回题目列表

Codeforces · 37/D

D. 课程时间表

中文机器翻译题面 查看原题

当 Petya 没有玩电脑游戏的时间时,他会去上大学课程。佩蒂亚学院每天的课程包括两节双节课。上课的楼层是一条长长的走廊,沿着走廊有M间教室,编号从1到M。

Petya同年级的所有学生被分为N组。 Petya最近注意到,这些小组的时间表有以下特点:第一节课的教室编号不会超过第二节课的教室编号。

有一次,Petya 决定计算一下可以为所有这些小组制定课程时间表的方法的数量。时间表是一组 2N 个数字:对于每个组,第一课和第二课进行的房间数。不幸的是,他很快就失去了计算的轨迹,并决定只计算满足以下条件的时间表:

1) 在课堂的第一节课中,i 组必须出席。

2) 在教室里,最多只能安排彝族小组。

帮助 Petya 计算满足所有这些条件的时间表数量ю 由于此类时间表可能有很多,因此输出模 109 + 7。

输入

第一行包含一个整数 M (1 ≤ M ≤ 100) — 教室数量。

第二行包含 M 个空格分隔的整数 — Xi (0 ≤ Xi ≤ 100) 第一课时教室 i 中出现的小组数量。

第三行包含 M 个空格分隔的整数 — Yi (0 ≤ Yi ≤ 100) 教室 i 中可以同时出现的最大组数。

保证所有Xi≤Yi,并且所有Xi之和为正且不超过1000。

输出

在单行中输出模 109 + 7 的问题答案。

示例

输入 #1

3
1 1 1
1 2 3

输出 #1

36

输入 #2

3
1 1 1
1 1 1

输出 #2

6

注意

在第二个样本测试中,每组的第一课和第二课必须在同一教室进行,这就是为什么时间表会有所不同,只是每组的教室编号重新排列,例如3! = 6。