RIOI_3_2  Counting
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:36 164 164
6 16
4 16
1 14
3 7
1 14Output: 0
27
14
2
hide comments
tuhin:
20130606 05:22:13
O(NM) should work fine gareev 

Gareev:
20130326 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?

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