AT_codefestival_2016_qualC_c 二人のアルピニスト

[problemUrl]: https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_c アルピニストである高橋君と青木君は最近ある有名な山脈を踏破しました。この山脈は$ 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 $を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ T_1 $ $ T_2 $ $ ... $ $ T_N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

山の高さの列としてありうるものが何通りあるかを $ 10^9+7 $ で割ったあまりを出力せよ。

### 制約 - $ 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) $ ### Sample Explanation 1 山の高さの列として、 - $ 1,3,2,2,2 $ - $ 1,3,2,1,2 $ - $ 1,3,1,2,2 $ - $ 1,3,1,1,2 $ の$ 4 $通りがありえます。 ### Sample Explanation 2 高橋君によると山を全て登り切った後の山の高さの最大値は$ 2 $で、青木君によると$ 3 $なので、記録は矛盾しています。 ### Sample Explanation 3 $ 10^9+7 $ で割ったあまりを求めることを忘れないようにしてください。 ### Sample Explanation 4 山が一つの山脈もあります。