当 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。