3027: 数据宝
题目描述
小W正在和众人筹办一场模拟赛，他的主要任务是造数据。
这点小事并不能难倒小W，很快他就造完了数据。在造数据的过程中，他注意到了一个有趣的问题：他发现符合题目要求的合法数据非常特殊，它是 一个n维空间中满足两点间切比雪夫距离最大值等于D的点集。那么这样的点集有多少个呢?
很快小W意识到自己的问题很愚蠢，因为这样的点集有无数个。不过他马上想到了另外一个问题：若两个点集可以通过平移互相得到，那么它们被认为是等价的。那么一共会有多少个不同的等价类呢?
答案数可能很大，所以你只要告诉小W模1000000007(109 + 7)后的答案的值。
输入
第一行一个整数T，表示数据组数。
接下来T行每行两个整数n和D,表示一组数据。
输出
共T行，每行一个整数表示答案。
样例输入 复制
5
2 1
1 10
2 2
3 1
3 2样例输出 复制
9
512
390
217
133443110提示
【解释与提示】
1 n维空间中两点的切比雪夫距离等于两点各项坐标差绝对值的最大值。
2 两个点集 X, Y 可以通过平移互相得到，则它们是等价的。更准确的说，这两个点集点数相等，且存在一个n元组(t1, t2, ..., tn)使得X中每个点对应分量加上 ti 后等于 Y 。例如：
– {(0, 1), (3, 0)} 和 {(2, 2), (5, 1)}。
– {(3, 0, 2), (0, 1, 1), (2, 3, 0)} 和 {(3, 1, 3), (0, 2, 2), (2, 4, 1)}
– {(0, 3, 1), (0, 0, 2), (2, 2, 0)} 和 {(3, 5, 2), (3, 2, 3), (5, 4, 1)}
【样例解释】
对于第一组数据的九个点集等价类：
• {(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)}
有10%的数据：n = 1
另有10%的数据：D = 1
另有10%的数据：n = 2
另有10%的数据：D = 2
60%的数据：1 ≤ n ≤ 15
100%的数据：1 ≤ T ≤ 10 ; 1 ≤ n ≤ 1000 ; 1 ≤ D ≤ 109