DP + Maths


You have “N” shinigamis and “M” apples. You need to give a positive number of apples to every shinigami and also make sure that every shinigami receives a distinct number of apples. Find out the number of ways in which you can distribute all M apples. Two ways are same if every shinigami gets the same number of apples.

Input Format:

The first line contains “T” , the number of test cases. Each of the next “T” lines contains two integers, “N” and “M” , as stated in the question.

Output Format:

For each of the “T” test cases, output the required ans. Since the answer can be very big , output it modulo 10^9 + 7 (1000000007).


1 <= T <= 10^5
1 <= N <= 300
1 <= M <= 100000

Sample Input:

1 2
2 2

Sample Output:


Sample Explanation:

Test case #1:
We have only one basket , where we can put the 2 apples. This can be done in only one way.

Test case #2:
We have two baskets but only two apples. We cannot obtain a partition with distinct and positive apples for each shinigami.