Hippity Hoppity

# E. Hippity Hoppity

#### 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$$.

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

#### Constraints

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$$.

5 1 1 2
3

500000004

#### 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. lexmathcsclub@gmail.com LIT Discord Server