Journey through Lithuanian Cities

You are in Vilnius (city 1) and wish to visit different Lithuanian cities located along a straight line from 1 to N. Each city has a train station with a monorail route. You can board a train only at its originating station. The train from city i stops every \(d_i\) cities, making \(x_i\) stops (excluding the starting city). If \(d_i = 0\), the train is out of service and cannot be used.

Specifically, if you board the train at city i, you may get off at any city numbered \(i + t \times d_i\) where \(1 \le t \le x_i\) and \(i + t \times d_i \le N\). Two journeys are considered different if the sequence of cities at which you disembark is different.

Calculate the total number of different journeys starting from city 1, and output the answer modulo \(10^9+7\).

inputFormat

The first line contains an integer N, the number of cities. The second line contains N space-separated integers: (d_1, d_2, \dots, d_N). The third line contains N space-separated integers: (x_1, x_2, \dots, x_N).

outputFormat

Output a single integer: the number of different journeys modulo (10^9+7).

sample

5
1 2 0 1 0
2 1 0 2 0

4