Workbook Algorithms

A company known for its printed workbooks decided to publish a new coding workbook for elementary school students. Parents who had no idea how to teach coding at home welcomed the news.

Junseo was picked for the writing team. He did not think much of the trend at first, but an offer of 50,000 won per problem changed his mind.

Junseo took the graph algorithms unit and came up with the following problem.

For a permutation $P$ of $1$ through $N$, define an undirected graph $G(P)$ on $N$ vertices as follows. For each $i$, draw one edge joining vertex $i$ and vertex $P_i$. Self loops and repeated edges are allowed. Given an undirected graph $X$ on $N$ vertices, find every permutation $P$ with $G(P) = X$.

Junseo wants the number of permutations that answer the problem to be neither too small nor too large, so he uses a graph $X$ only when the number of permutations $P$ with $G(P) = X$ is at least $l$ and at most $r$. He wants the money, so he uses every graph $X$ that meets the bound.

The vertices are numbered $1$ through $N$, and two graphs count as different when their edges differ. How many problems can Junseo publish?

The first line contains three integers $N$, $l$, $r$ ($1 \le N \le 200\,000$, $1 \le l \le r \le 10^9$).

Print on one line the number of distinct problems Junseo can publish, that is the number of graphs $X$ meeting the bound, modulo $10^9+7$.