Informatica Online Judge

  구몬 알고리즘 [2159 / 086F]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 2   Total Tried : 2


The Champion of this Problem (C++) : gs17068 - 0ms / 1189byte
My Best Submission (C++) : N/A

[koistudy.net(33rd 김동현)]

Background

학습지의 대명사 구몬에서는 요즘 화제인 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$만 문제로 내고 싶다. 구사과는 돈을 많이 벌고 싶기 때문에 기준에 맞는 문제라면 모조리 낼 것이다. 구사과는 신사임당 지폐를 몇 장 받을 수 있을까?

Input

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

Output

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

IO Example

입력
3 1 2

출력
5

입력2
4 2 3

출력2
7

입력3
4 5 7

출력3
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]