← 返回题目列表

AtCoder · codefestival_2016_qualC_c

C. 两名登山运动员

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

分数: 400 点

问题陈述

登山家高桥先生和青木先生最近徒步穿越了某座著名的山脉。 山脉由 N 山脉,从西向东呈直线延伸,如富士山。 1,山。 2, ..., 山。 N。 高桥先生从西边穿越了山脉,青木先生从东边穿越了山脉。

富士山的高度 i is h_i,但他们忘记了每个的价值 h_i。 相反,对于每个 i (1 ≤ i ≤ N),他们记录了到达珠穆朗玛峰顶峰时所攀登的最高山峰高度。 i (包括山) i)。 高桥先生的记录是 T_i 青木先生的记录是 A_i.

我们知道每座山的高度 h_i 是正整数。 计算山脉高度的可能序列数,模数 10^9 + 7.

请注意,记录可能不正确,因此可能没有可能的山脉高度顺序。 在这种情况下,输出 0.

约束

  • 1 ≤ N ≤ 10^5
  • 1 ≤ T_i ≤ 10^9
  • 1 ≤ A_i ≤ 10^9
  • T_i ≤ T_{i+1} (1 ≤ i ≤ N - 1)
  • A_i ≥ A_{i+1} (1 ≤ i ≤ N - 1)

输入

输入由标准输入按以下格式给出:

N
T_1 T_2 ... T_N
A_1 A_2 ... A_N

输出

打印山脉高度的可能序列数,模数 10^9 + 7.


示例输入 1

5
1 3 3 3 3
3 3 2 2 2

示例输出 1

4

山脉高度的可能顺序是:

  • 1, 3, 2, 2, 2
  • 1, 3, 2, 1, 2
  • 1, 3, 1, 2, 2
  • 1, 3, 1, 1, 2

总共四个序列。


示例输入 2

5
1 1 1 2 2
3 2 1 1 1

示例输出 2

0

记录是矛盾的,因为高桥先生记录了 2 作为爬完所有山峰后的最高峰,但青木先生记录 3.


示例输入 3

10
1 3776 3776 8848 8848 8848 8848 8848 8848 8848
8848 8848 8848 8848 8848 8848 8848 8848 3776 5

示例输出 3

884111967

不要忘记计算数字模数 10^9 + 7.


示例输入 4

1
17
17

示例输出 4

1

有些山脉仅由一座山组成。