Randomly Sorted

Moderate

0/80

Average time to solve is 35m

Contributed by

7 upvotes

Problem statement

Let us say you randomly choose 'N' non-negative integers less than 'M' and put them in an array 'A'.

Find the probability that 'A' is sorted in non-decreasing order.

The answer should be found modulo 10^9 + 7. Formally, let M = 10^9 + 7. It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are integers and q !≡ 0 (mod M). Output the integer equal to p * (q^-1) mod M. In other words, output such an integer x that 0 <= x < M and x * q ≡ p (mod M).

For Example :

Let 'N' = 3, 'M' = 3.
There are 27 possible final arrays.
10 of them are sorted in non-decreasing order: [ '0, 0, 0' ], [ '1, 1, 1' ], [ '2, 2, 2' ], [ '0, 1, 2' ], [ '0, 0, 1' ], [ '0, 1, 1' ], [ '0, 0, 2' ], [ '0, 2, 2' ], [ '1, 1, 2' ], [ '1, 2, 2' ].
Thus the probability needed is '(10 / 27) % (10^9 + 7) = 703703709'.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains a single integer 'T', which denotes the number of test cases.
Then 'T' test cases follow. For each test case:

The first and only line contains two integers, 'N' and 'M'.

Output Format :

For each test case, return the probability that 'A' is sorted in non-decreasing order, modulo 10^9 + 7.

Note :

You don’t need to print anything. Just implement the given function.

Constraints :

1 <= 'T' <= 10
2 <= 'N, M' <= 10^3

Time Limit: 1 sec

Sample Input 1 :

2
3 5
2 2

Sample Output 1 :

960000007
750000006

Explanation of sample input 1 :

First test case:-
There are '5^3 = 125' possible final arrays.
Out of the arrays with 'A[ 0 ] = 0', exactly '15' are sorted in non-decreasing order.
For arrays with 'A[ 0 ] = 1', exactly '10' are sorted in non-decreasing order.
For arrays with 'A[ 0 ] = 2', exactly '6' are sorted in non-decreasing order.
For arrays with 'A[ 0 ] = 3', exactly '3' are sorted in non-decreasing order.
For arrays with 'A[ 0 ] = 4', exactly '1' is sorted in non-decreasing order.
Thus, the answer is '(35 / 125) % (10^9 + 7) = 960000007'.

Second test case:-
There are 4 possible final arrays.
3 of them are sorted in non-decreasing order: [ '0, 0' ], [ '0, 1' ], [ '1, 1' ].
Thus, the answer is '(3 / 4) % (10^9 + 7) = 750000006'.

Sample Input 2 :

2
25 43
60 29

Sample Output 2 :

43816143
973827568

Console