No.645 Count Permutation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 15
作問者 : PulmnPulmn / テスター : yosupotyosupot
1 ProblemId : 1864 / 出題時の順位表

問題文

以下の条件を満たす $(1,2,\dots ,N)$ の順列 $A$ の通り数を求めてください。ただし、この値は非常に大きくなる場合があるので $1{,}000{,}000{,}007$ で割った時の余りを出力してください。

条件:$f(B)=A$ を満たす $(1,2,\dots ,N)$ の順列 $B$ の通り数が $L$ 以上 $R$ 以下になる。ただし、$f(B)$ は $B$ に次の操作を行った順列とします。

操作:$i=1,2,\dots ,N-1$ という順番で $B_i\gt B_{i+1}$ ならば、$B_i$ の値と $B_{i+1}$ の値を入れ替える。

入力

$N$ $L$ $R$

$2\le N\le 10^5,0\le L\le R\le 10^{18}$

出力

条件を満たす順列 $A$ の通り数を $1{,}000{,}000{,}007$ で割った時の余りを出力してください。最後に改行してください。

サンプル

サンプル1
入力
5 2 7
出力
17

$B=\{2,4,1,3,5\}$ として上記の操作を行ってみます。
$i=1$ のとき $B_i \lt B_{i+1}$ なので何もしない。
$i=2$ のとき $B_i \gt B_{i+1}$ なので $B=\{2,1,4,3,5\}$ になる。
$i=3$ のとき $B_i \gt B_{i+1}$ なので $B=\{2,1,3,4,5\}$ になる。
$i=4$ のとき $B_i \lt B_{i+1}$ なので何もしない。
したがって、$f(\{2,4,1,3,5\})=\{2,1,3,4,5\}$ になります。
また、条件を満たす順列 $A$ として、$A=\{3,4,2,1,5\},\{4,2,3,1,5\}$ などがあります。

サンプル2
入力
10 0 3628800
出力
3628800

$10!=3628800$ なので、条件を満たす順列 $A$ は $(1,2,\dots ,10)$ の順列全てです。

サンプル3
入力
1000 1000 1000
出力
0

出力する値が $0$ の場合もあります。

サンプル4
入力
100 1000000000 1000000000000000000
出力
2041684

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。