Hippity Hoppity

E. Hippity Hoppity

No Submission Yet

Problem Statement

Hannah loves to hop! She is on LHS's quad, which is a road consisting of infinite bricks. She starts on the first brick. On each move, she randomly chooses a number \(x\) between [\(l\),\(r\)] inclusively with equal probability, and jumps from the \(i\)th brick to the \((i+x)\)th brick. However, due to the recent snowstorm, \(M\) of the bricks are blocked by snow, so if the number Hannah chooses leads to a blocked brick, she will discard her initial number and pick again. Furthermore, if she ever lands on bricks with number less than \(1\) or greater than \(N\), she immediately stops because she believes she has hopped too far away.

Find the probability that she will at some point be exactly on the \(N\)th brick given enough time, under modulo \(10^9 + 7\). Note that fraction \(\frac{p}{q}\) equals to \(p \cdot q^{-1}\) where \(q^{-1}\) is the modular inverse of \(q\).

Additional Notes

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 128mb


For testcases \(1\) - \(9\), \(1 \leq M \leq N \leq 10^5\) and \(0 \leq L \leq R \leq N\).
There is also a bonus testcase \(10\) that is significantly harder than the others. Its constraints are \(1 \leq M \leq N \leq 500\) and \(-N \leq L \leq R \leq N\).

Input format

The first line contains four integers, \(N\), \(M\), \(L\), \(R\)
The following line contains \(M\) numbers, \(b_i\) means that the \(b_i\)th brick is blocked.

Output format

The output should be one integer, the probability that Hannah ever lands on the \(N\)th brick under modulo \(10^9+7\).

Sample input:

5 1 1 2

Sample output


Sample Explanation

For the first move, Hannah can only jump onto brick \(2\), because brick \(3\) is blocked. Then Hannah's only option is to jump onto brick \(4\) for the same reason. Finally, Hannah can choose to either jump onto brick \(5\) or brick \(6\). Jumping onto brick \(6\) would render the task impossible, so there is a 50% chance for Hannah to land on brick \(5\), which is 500000004 under modulo.

Contact Us
LIT Discord Server