RIOI_3_2 - Counting

no tags 

Given integers N and M, output in how many ways you can take N distinct positive integers such that sum of those integers is <= M. Since the result can be huge, output it modulo 1000000007 (10^9 + 7)

N <= 20 

M <= 100000

Input

First line of input is number t, number of test cases. Each test case consists only of 2 numbers N and M, in that order.

Output

Output the answer asked for in the description.

Example

Input:
4
6 16
4 16
1 14
3 7

Output:
0
27
14
2

hide comments
Shubhojeet Chakraborty: 2018-08-28 08:44:54

Must do problem!
Had fun solving this.

Last edit: 2018-08-28 08:45:13
tuhin: 2013-06-06 05:22:13

O(NM) should work fine gareev


Added by:Buda IM
Date:2012-12-08
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Known Problem