Company: wipro_2nov
Difficulty: medium
Drone Upgrade Sequence Planner A production line has n drone models in a fixed order. Model i must be given an upgrade level c[i] , and that level has to stay inside the model's own window: a[i] <= c[i] <= b[i] . A later model must never be weaker than an earlier one, so the chosen levels have to be non-decreasing: c[0] <= c[1] <= ... <= c[n-1] . Count the upgrade plans c that satisfy both rules. The number can be enormous, so report it modulo 10^9 + 7 . Input Format The first line contains an integer n . Each of the next n lines contains one integer, giving the array a in order. The next line contains the integer n again. Each of the next n lines contains one integer, giving the array b in order. Output Format Print a single integer -- the number of valid upgrade plans, taken modulo 10^9 + 7 . Constraints 1 <= n <= 1000 1 <= a[i] <= b[i] <= 1000 a is non-decreasing: a[i] <= a[j] whenever i < j . Examples Example 1 Input: 2 1 1 2 2 3 Output: 5 Explan