{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/JAN14/mandarin/CNTDSETS.pdf\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/JAN14/russian/CNTDSETS.pdf\"\u003eRussian\u003c/a\u003e.\u003c/h3\u003e\r\n\u003cp\u003eChef likes points located at integer coordinates in a space having \u003cb\u003eN\u003c/b\u003e dimensions. In particular, he likes sets of such points having diameter \u003cb\u003eexactly equal to D\u003c/b\u003e (called \u003cit\u003eD-sets\u003c/it\u003e). The diameter of a set of points is the maximum distance between any pair of points in the set. The distance between two points \u003cb\u003e(a\u003csub\u003e1\u003c/sub\u003e,a\u003csub\u003e2\u003c/sub\u003e,...,a\u003csub\u003eN\u003c/sub\u003e)\u003c/b\u003e and \u003cb\u003e(b\u003csub\u003e1\u003c/sub\u003e,b\u003csub\u003e2\u003c/sub\u003e,...,b\u003csub\u003eN\u003c/sub\u003e)\u003c/b\u003e is \u003cb\u003emax{|a\u003csub\u003e1\u003c/sub\u003e-b\u003csub\u003e1\u003c/sub\u003e|, |a\u003csub\u003e2\u003c/sub\u003e-b\u003csub\u003e2\u003c/sub\u003e|, ..., |a\u003csub\u003eN\u003c/sub\u003e-b\u003csub\u003eN\u003c/sub\u003e|}\u003c/b\u003e.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nChef would like to know how many D-sets exist. However, he soon realized that, without any extra constraints, there is an infinite number of D-sets. Thus, he would only like to count the number of classes of D-sets, such that any two D-sets which belong to the same class are equivalent under translation. To be more precise, two D-sets \u003cb\u003eX\u003c/b\u003e and \u003cb\u003eY\u003c/b\u003e are considered equivalent (and belong to the same class) if:\u003cul\u003e\r\n\u003cli\u003ethey contain the same number of points \u003cb\u003eAND\u003c/b\u003e\r\n\u003cli\u003ethere exists a tuple of \u003cb\u003eN\u003c/b\u003e integer numbers \u003cb\u003e(t\u003csub\u003e1\u003c/sub\u003e, ..., t\u003csub\u003eN\u003c/sub\u003e)\u003c/b\u003e such that by translating each point of \u003cb\u003eX\u003c/b\u003e by the amount \u003cb\u003et\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e in dimension \u003cb\u003ei\u003c/b\u003e (\u003cb\u003e1≤i≤N\u003c/b\u003e) we obtain the set of points \u003cb\u003eY\u003c/b\u003e.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nLet\u0027s consider \u003cb\u003eN\u003d2\u003c/b\u003e, \u003cb\u003eD\u003d4\u003c/b\u003e and the following sets of points \u003cb\u003eX\u003d{(1,2), (5,5), (4,3)}\u003c/b\u003e and \u003cb\u003eY\u003d{(2,5), (5,6), (6,8)}\u003c/b\u003e. Let\u0027s consider now the tuple \u003cb\u003e(1,3)\u003c/b\u003e. By translating each point of \u003cb\u003eX\u003c/b\u003e by the amounts specified by this tuple we obtain the set \u003cb\u003e{(2,5), (6,8), (5,6)}\u003c/b\u003e, which is exactly the set \u003cb\u003eY\u003c/b\u003e. Thus, the two sets \u003cb\u003eX\u003c/b\u003e and \u003cb\u003eY\u003c/b\u003e are equivalent and belong to the same class.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nHelp Chef find the number of classes of D-sets \u003cb\u003emodulo 1000000007\u003c/b\u003e (\u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e+7\u003c/b\u003e).\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of input contains the number of test cases \u003cb\u003eT\u003c/b\u003e. Each of the next \u003cb\u003eT\u003c/b\u003e lines contains two space-separated integers describing a test case: \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eD\u003c/b\u003e.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case (in the order given in the input), output the number of classes of D-sets \u003cb\u003emodulo 1000000007\u003c/b\u003e.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cp\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eT\u003c/b\u003e ≤ \u003cb\u003e10\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e1000\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eD\u003c/b\u003e ≤ \u003cb\u003e1000000000\u003c/b\u003e (\u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e\u003c/b\u003e)\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\r\n5\r\n1 10\r\n2 1\r\n2 10\r\n3 1\r\n3 3\r\n\u003c/pre\u003e\r\n\u003cp\u003e \u003c/p\u003e\r\n\u003cpre\u003e\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n512\r\n9\r\n498134775\r\n217\r\n548890725\r\n\u003c/pre\u003e\r\n\u003cp\u003e \u003c/p\u003e\r\n\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\u003cp\u003e\u003cb\u003eExample case 1:\u003c/b\u003e\r\nWhen \u003cb\u003eN\u003d1\u003c/b\u003e all the points are arranged in a line. In order to have a diameter equal to \u003cb\u003e10\u003c/b\u003e each D-set must contain two points at distance \u003cb\u003e10\u003c/b\u003e. Between two such points there may be up to \u003cb\u003e9\u003c/b\u003e points which may belong to the D-set or not. Thus, there are \u003cb\u003e2\u003csup\u003e9\u003c/sup\u003e\u003d512\u003c/b\u003e classes of D-sets.\r\n\u003c/p\u003e\r\n\u003cp\u003e\u003cb\u003eExample case 2:\u003c/b\u003e\r\nThere are \u003cb\u003e9\u003c/b\u003e classes of D-sets. One D-set from each class is given below:\u003cul\u003e\r\n\u003cli\u003e{(0,0), (0,1)}\u003c/li\u003e\r\n\u003cli\u003e{(0,0), (1,0)}\u003c/li\u003e\r\n\u003cli\u003e{(0,0), (1,1)}\u003c/li\u003e\r\n\u003cli\u003e{(0,1), (1,0)}\u003c/li\u003e\r\n\u003cli\u003e{(0,0), (0,1), (1,0)}\u003c/li\u003e\r\n\u003cli\u003e{(0,0), (0,1), (1,1)}\u003c/li\u003e\r\n\u003cli\u003e{(0,0), (1,0), (1,1)}\u003c/li\u003e\r\n\u003cli\u003e{(0,1), (1,0), (1,1)}\u003c/li\u003e\r\n\u003cli\u003e{(0,0), (0,1), (1,0), (1,1)}\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e"}}]}