tjoi2012 图同构

时间限制:10s      空间限制:128MB

题目描述

两个图同构的判定问题目前还没有高效的算法。不过有这样一种方法,如果两个图,度为0的点的个数 
相同,度为1的点的个数相同,度为2的点的个数相同……那么就认为两个图同构,但是这样一种方法并非总 
是正确的。现要求出,n个点,每个点的度不超过K,没有自环的图被上述算法分为了多少种。 


输入格式

第一行,一个整数T 
接下来T行,每行两个整数n,k 


输出格式

T行,在n和k的限制下,有多少种图,由于此数可能过大,输出其对1,000,000,009的余数


样例输入

3 
3 2 
2 3 
4 2

样例输出

5 
4 
8 

提示

对应n-3,k-2有 
V={I,2,3) 
E={),{(1,2)),{(1,2),(1,2)),{(1,2),(2,3)),{(1,2),(2,3),(1,3)) 
l<=n,k<= 1000,l<=t<=3
请不要提交,错误数据.求正确数据!


题目来源

没有写明来源