학습지 알고리즘

학습지로 유명한 회사가 초등학생용 코딩 학습지를 새로 만들기로 했다. 아이에게 코딩을 어떻게 가르쳐야 할지 몰라 난감해하던 학부모는 이 소식을 반겼다.

집필진으로 뽑힌 준서는 처음에는 이런 유행을 탐탁지 않아 했지만, 문제 하나당 5만원을 주겠다는 제안에 마음을 바꿨다.

그래프 알고리즘 단원을 맡은 준서는 다음 문제를 생각해 냈다.

$1$부터 $N$까지의 순열 $P$에 대해, 정점이 $N$개인 무방향 그래프 $G(P)$를 다음과 같이 정의한다. 각 $i$마다 정점 $i$와 정점 $P_i$를 잇는 간선을 하나씩 긋는다. 셀프 루프와 중복 간선도 허용한다. 정점이 $N$개인 무방향 그래프 $X$가 주어지면, $G(P) = X$인 순열 $P$를 모두 구하라.

준서는 답이 되는 순열이 너무 적지도, 너무 많지도 않기를 바란다. 즉 $G(P) = X$인 $P$가 $l$개 이상 $r$개 이하인 $X$만 문제로 낸다. 돈을 많이 벌고 싶으므로 기준에 맞는 $X$는 하나도 빠뜨리지 않고 문제로 낸다.

정점에는 $1$부터 $N$까지 번호가 붙어 있고, 간선의 구성이 다르면 서로 다른 그래프로 센다. 준서는 문제를 몇 개나 낼 수 있을까?

첫째 줄에 세 정수 $N$, $l$, $r$이 주어진다. ($1 \le N \le 200\,000$, $1 \le l \le r \le 10^9$)

준서가 낼 수 있는 서로 다른 문제의 수, 즉 조건을 만족하는 그래프 $X$의 개수를 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.