問題文

アルピニストである高橋君と青木君は最近ある有名な山脈を踏破しました。この山脈は$N$ 個の山からなっており、西から東に向けて山$1$,山$2$,$...$,山$N$と一直線に並んでいます。高橋君は西から、青木君は東からこの山脈を踏破しました。

山$i$ の高さは$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$

の$4$通りがありえます。

---

入力例 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

山が一つの山脈もあります。