#P1874E. Jellyfish and Hack
Jellyfish and Hack
No submission language available for this problem.
Description
It is well known that quick sort works by randomly selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. But Jellyfish thinks that choosing a random element is just a waste of time, so she always chooses the first element to be the pivot. The time her code needs to run can be calculated by the following pseudocode:
function fun(A)
if A.length > 0
let L[1 ... L.length] and R[1 ... R.length] be new arrays
L.length = R.length = 0
for i = 2 to A.length
if A[i] < A[1]
L.length = L.length + 1
L[L.length] = A[i]
else
R.length = R.length + 1
R[R.length] = A[i]
return A.length + fun(L) + fun(R)
else
return 0
Now you want to show her that her code is slow. When the function is greater than or equal to , her code will get . You want to know how many distinct permutations of satisfies . Because the answer may be large, you will only need to find the answer modulo .
The only line of the input contains two integers and (, ).
Output the number of different permutations that satisfy the condition modulo .
Input
The only line of the input contains two integers and (, ).
Output
Output the number of different permutations that satisfy the condition modulo .
Note
In the first example, satisfies the condition, because:
Do remember to output the answer modulo .