Counting Dsets

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef likes points located at integer coordinates in a space having N dimensions. In particular, he likes sets of such points having diameter exactly equal to D (called Dsets). The diameter of a set of points is the maximum distance between any pair of points in the set. The distance between two points (a_{1},a_{2},...,a_{N}) and (b_{1},b_{2},...,b_{N}) is max{a_{1}b_{1}, a_{2}b_{2}, ..., a_{N}b_{N}}.
Chef would like to know how many Dsets exist. However, he soon realized that, without any extra constraints, there is an infinite number of Dsets. Thus, he would only like to count the number of classes of Dsets, such that any two Dsets which belong to the same class are equivalent under translation. To be more precise, two Dsets X and Y are considered equivalent (and belong to the same class) if:
 they contain the same number of points AND
 there exists a tuple of N integer numbers (t_{1}, ..., t_{N}) such that by translating each point of X by the amount t_{i} in dimension i (1≤i≤N) we obtain the set of points Y.
Let's consider N=2, D=4 and the following sets of points X={(1,2), (5,5), (4,3)} and Y={(2,5), (5,6), (6,8)}. Let's consider now the tuple (1,3). By translating each point of X by the amounts specified by this tuple we obtain the set {(2,5), (6,8), (5,6)}, which is exactly the set Y. Thus, the two sets X and Y are equivalent and belong to the same class.
Help Chef find the number of classes of Dsets modulo 1000000007 (10^{9}+7).
Input
The first line of input contains the number of test cases T. Each of the next T lines contains two spaceseparated integers describing a test case: N and D.
Output
For each test case (in the order given in the input), output the number of classes of Dsets modulo 1000000007.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 1000
 1 ≤ D ≤ 1000000000 (10^{9})
Example
Input: 5 1 10 2 1 2 10 3 1 3 3
Output: 512 9 498134775 217 548890725
Explanation
Example case 1:
When N=1 all the points are arranged in a line. In order to have a diameter equal to 10 each Dset must contain two points at distance 10. Between two such points there may be up to 9 points which may belong to the Dset or not. Thus, there are 2^{9}=512 classes of Dsets.
Example case 2:
There are 9 classes of Dsets. One Dset from each class is given below:
 {(0,0), (0,1)}
 {(0,0), (1,0)}
 {(0,0), (1,1)}
 {(0,1), (1,0)}
 {(0,0), (0,1), (1,0)}
 {(0,0), (0,1), (1,1)}
 {(0,0), (1,0), (1,1)}
 {(0,1), (1,0), (1,1)}
 {(0,0), (0,1), (1,0), (1,1)}
Author:  mugurelionut 
Editorial  http://discuss.codechef.com/problems/CNTDSETS 
Tags  combinatorics, hard, inclusnexclusn, jan14, mugurelionut 
Date Added:  28082013 
Time Limit:  0.3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions