No.645 Count Permutation
Pulmn
yosupotProblem Statement
Find the number of permutations $A$ of $(1,2,\dots ,N)$ that satisfy the following condition. Since this value can be very large, output it modulo $1{,}000{,}000{,}007$.
Condition: The number of permutations $B$ of $(1,2,\dots ,N)$ satisfying $f(B)=A$ is at least $L$ and at most $R$. Here, $f(B)$ is the permutation obtained by performing the following operation on $B$.
Operation: In the order $i=1,2,\dots ,N-1$, if $B_i\gt B_{i+1}$, swap the values of $B_i$ and $B_{i+1}$.
Input
$N$ $L$ $R$
$2\le N\le 10^5,0\le L\le R\le 10^{18}$
Output
Output the number of permutations $A$ satisfying the condition, modulo $1{,}000{,}000{,}007$. Print a newline at the end.
Sample
Sample 1
Input
5 2 7
Output
17
Let us perform the above operation with $B=\{2,4,1,3,5\}$.
For $i=1$, $B_i \lt B_{i+1}$, so nothing is done.
For $i=2$, $B_i \gt B_{i+1}$, so $B=\{2,1,4,3,5\}$.
For $i=3$, $B_i \gt B_{i+1}$, so $B=\{2,1,3,4,5\}$.
For $i=4$, $B_i \lt B_{i+1}$, so nothing is done.
Therefore, $f(\{2,4,1,3,5\})=\{2,1,3,4,5\}$.
Examples of permutations $A$ satisfying the condition include $A=\{3,4,2,1,5\},\{4,2,3,1,5\}$.
Sample 2
Input
10 0 3628800
Output
3628800
Since $10!=3628800$, all permutations of $(1,2,\dots ,10)$ satisfy the condition as $A$.
Sample 3
Input
1000 1000 1000
Output
0
The value to output may be $0$.
Sample 4
Input
100 1000000000 1000000000000000000
Output
2041684
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。