HDU 5779 Tower Defence(dp+组合数)

题目链接就：
HDU 5779 Tower Defence
题意：
小白最近痴迷于玩Tower Defence。他想要自己制作一张地图。地图是一张有n个点的无向图（图可以不连通,没有重边和自环），所
有边的长度都为1，满足从1号点到其他任意一个点的最短路都不等于k.小白想知道这样的图有多少个。如果两个顶点不连通，那么它
们之间的距离为无穷大。答案对$10^9+7$取模。
数据范围：$n\leq 60, k\leq 60$
分析：
从1号点到其他任意点的最短路都不等于$k$，所以对于能从1号点到达的点的最短路都是小于$k$的，所以可以把点分成两个部分:1号点可达和1号点不可达。
对于1号点可达的点我们枚举最短路$j$，显然对于所有最短路为$j$的点，1号点到达它们之前必然经过最短路为$j-1$的点，但是我们还需要知道最短路$\leq j$和最短路为$j$的点的个数，因此可以定义状态:
$dp[j][i][q]$表示最短路小于等于$j$的点一共有$i$个，其中最短路为