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 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 number aksed in description.

Example

Input:
3
6 16
4 16
4
6 16
4 16
1 14
3 7
1 14
Output: 0
27
14
2

hide comments
tuhin: 2013-06-06 05:22:13

O(NM) should work fine gareev

Gareev: 2013-03-26 23:05:33

I am getting TLE using iterative DP in O(N * M * sqrt(M)) algorithm. Can anyone give me hints about improvements or more efficient solutions?

RE (Author) : Read the notes below, we have forum for hints.

Last edit: 2012-12-30 16:42:00

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