Description
The midterm is coming.
However, as a lazy CS student, John doesn’t want to make an effort to review lectures from handouts or notes. He decides to do questions from the past exams.
There’re N past exams John has collected from his firends.
The number of questions in the i-th past exam is xi.
It’s very dangerous to take only one past exam for certain lectures.
Therefore, John picks yi questions from the i-th past exam to form a practice for himself.
In other words, there will be 
kinds of selections for the i-th past exam.
Can you find how many kinds of practices John may take?
If you can, John will give you his past-exam collections to make you get A+ in every exam.
Because the result may be too large to represent in computer, you’re asked to print the result module 10007, which means you should answer “70” if result = 10077.
Suggestion for 3rd ~ 5th testcases
Input
There’re 3 lines for input.
The first line has one number N, representing the number of past exams.
There’re x1,x2,...,xN and y1,y2,...,yN on the second and third lines, respectively, denoting the total numbers of questions and the numbers of picked questions in the past exams.
It is guaranteed that:
- 1 ≤ N ≤ 105
- 0 ≤ yi ≤ xi ≤ 100, xi != 0
Output
Let Z = the number of possible kinds of practices.
Because Z may be too large to represent in computer,
please print Z module 10007 ( Z % 10007 ) in one line, which means you should print “70” if Z = 10077.
Remember the ‘\n’ on the end of line.
Explaination of Sample
x1, x2 = 4, 3. y1, y2 = 1, 2
There’re 4 and 3 kinds of selections from the 1-st and 2-nd past exams.
Therefore, there’re 4*3 = 12 kinds of practices.