시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 30 18 16 61.538%

문제

학습지의 대명사 구몬에서는 요즘 화제인 4차 산업혁명의 물결을 따라 얼마 전 '구몬 알고리즘' 학습지를 만들겠다고 발표했다. 아이들에게 코딩 교육을 어떻게 해야 좋을지 몰라 쩔쩔매던 학부모들은 이에 크게 열광했다.

카이스트의 자랑 구사과는 구몬 알고리즘 집필진 중 한 명으로 뽑히게 되었다. 평소 4차 산업혁명이란 말을 별로 탐탁지 않아했던 구사과는 처음에는 거절했지만, 한 문제당 5만원씩 주겠다는 구몬 측의 유혹에 홀라당 넘어가 버리고 말았다. 역시 자본주의 사회에서는 돈이 최고인 법...

그래프 알고리즘 분야를 맡게 된 구사과는 다음과 같은 문제를 생각해 냈다.

'$1$부터 $N$까지의 순열 $P$에 대해, 정점이 $N$개인 그래프에서 모든 ($i$, $P_i$) 쌍에 대해 간선을 그은 무방향성 그래프를 $G(P)$라 하자. (셀프 루프, 중복 간선도 허용한다) 정점이 $N$개인 무방향성 그래프 $X$가 주어지면, $G(P)=X$인 $P$를 모두 구해라.'

구사과는 문제의 답이 되는 순열이 너무 적지도, 많지도 않았으면 한다, 즉, $G(P)=X$인 $P$가 $l$개 이상 $r$개 이하인 $X$만 문제로 내고 싶다. 구사과는 돈을 많이 벌고 싶기 때문에 기준에 맞는 문제라면 모조리 낼 것이다. 구사과는 신사임당 지폐를 몇 장 받을 수 있을까?

입력

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

출력

구사과가 낼 수 있는 서로 다른 문제의 수를 $10^9+7$로 나눈 나머지를 출력한다.

예제 입력 1

3 1 2

예제 출력 1

5

예제 입력 2

4 2 3

예제 출력 2

7

예제 입력 3

4 5 7

예제 출력 3

0