Time limit for problem R has increased to 3000ms, all solutions have been rejudged.
Ali is reading a story that has a challenge, if he solves it he can read the next story.
The first story says: In the year $10^9+7$ humans were not yet extinct, but instead, they found the $n^{th}$ dimension.
You are currently standing at some point $P$ in the $n$ dimensional space and you want to reach another point $Q$.
In one move you can choose a dimension $i$ (dimensions are 1-indexed), and increase the $i^{th}$ coordinate by $i$, more formally say you are currently standing at some point $A$ with coordinates $a_1,a_2,a_3,...,a_n$, if you choose the $i^{th}$ dimension, you will move to point $B$ with coordinates $a_1,a_2,...a_{i-1},a_i+i,a_{i+1},...a_n$.
Given the coordinates of $P$, $p_1,p_2,p_3,...p_n$ respectively, and the coordinates of $Q$, $q_1,q_2,q_3,...q_n$ respectively, count the number of different paths you can take to reach $Q$ starting from $P$, taken modulo $10^9+7$.
Two paths are considered different if there exists a point visited in one path but not in the other, or if the order of visited points is not the same.
Can you help Ali to solve this challenge?
The first line of input contains one integer $n$ ($1\le n \le 2\cdot 10^5$) , the number of dimensions.
The second line contains $n$ space seperated integers $p_1,p_2,p_3,...p_n$, ($0\le p \le 2\cdot 10^5$) the coordinates of the starting point $P$.
The third line contains $n$ space seperated integers $q_1,q_2,q_3,...q_n$, ($0\le q \le 2\cdot 10^5$) the coordinates of the ending point $Q$.
The output should contain one integer, the answer to the problem.
| Input | Output |
|---|---|
2 0 0 3 4 Copy
|
10 Copy
|
First of all note that for all integers $i\in [1,n]$, the $i^{th}$ coordinate can only increase so if $p_i>q_i$ it is impossible to reach $Q$ so the answer is clearly 0.
If $p_i\le q_i$ holds for all integers $i\in [1,n]$, we need to make exactly $m_i=\frac{q_i-p_i}{i}$ moves in the $i^{th}$ coordinate, so if there exists some dimension $i$ such that $q_i-p_i$ isn't divisible by $i$, then the answer is also 0.
Otherwise, we can certainly reach $Q$ making a total of $S=\sum_{i=1}^n m_i$ moves.
The number of different paths is equal to the number of ways to choose $m_1$ moves to be in the first dimension, and $m_2$ other moves to be in the second dimension,.... and $m_n$ other moves to be in the $n^{th}$ dimension, from the $S$ moves we are going to make.
This is equal to
$\frac{S!}{(m_1)!\cdot (m_2)!\cdot (m_3)!....(m_n)!}$
total complexity is $O(S)$, which is enough since $\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \le n\cdot \log_2n$.