SOLVE
LATER
John teaches a class of \(n \) students. Each student is assigned a unique roll number from \(1\) to \(n\). He also knows the heights of each student. He needs to select a set of class representatives (a class can have any number of representatives).
A set of students are valid candidates for representatives if the following condition holds:
John wants to select the maximum number of students as class representatives. However, he has a new student that got enrolled whose height is \(x\). In order to increase the number of class representatives, John assigns him a roll number \(i\) (from \(1\) to \(n+1\)) randomly and then increases the roll numbers of all those students by \(1\) whose roll number is \(\ge\) \(i\). If the number of class representatives does not increase after this process, then he repeats the same procedure (he again assigns him a roll number from \(1\) to \(n+1\) randomly after reverting the roll numbers of all the existing students from \(1\) to \(n\)). Determine the expected number of times John needs to repeat this procedure in order to increase the number of class representatives.
Input format
Output format
Print the expected number of times John needs to assign the roll number to the new student using the above procedure to increase the number of class representatives. If the expected value is of the form \(\frac{a}{b}\), then print \(a\cdot b^{-1}\) modulo \(10^{9}+7\) . If it is not possible to increase the number of class representatives, then print \(-1\).
Constraints
\(1 \le n \le 500000\)
\(1 \le r_i \le n\)
\(1 \le x,hi \le 10^7\)
The number of class representatives can be increased from 3 to 4 by assigning the new student roll number 3,4 or 5.