图

有一张含有n个点的无向完全图，其中每一条边都有\(1～L\)的权值。熊孩子想知道，有多少个这样的图，使得从 \(1\)到\(n\)的最短路为$ k$。

输出答案对\(10^9+7\)取模。

输入格式
第一行三个整数\(n,k,L\)
输出格式
一个整数表示答案。

样例1
input

3 3 3

output

8

数据范围
对于 20%的数据 \(n,k,L<=5\)
对于 另外20%的数据 \(n,k<=3,L<=10\)。

对于 60%的数据 \(n,k,L<=8\)
对于 80%的数据\(n,k,L<=12\)
对于 100%的数据 \(n,k<=12,L<=10^9\)
时间限制：1S

空间限制：128MB

n那么小，考虑暴力搜索。搜索方式是枚举每个点的最短路，然后考虑在这种情况下有多少种可能。我们设现在枚举出的\(1,2\cdots n\)最短路是\(a_1,a_2\cdots a_n\)，然后排一边序，一个点的最短路能来自前面的点转移。前面的\(j\)到\(i\)的距离不能小于\(a_j\)和\(a_i\)的差，所以有\(l-(a_j-a_i)+1\)种可能性。但是还要减去全部小于\(a_j-a_i\)的情况，不然的话\(i\)的最短路不是\(a_i\)。

那些最短路大于等于\(k\)的很明显除了\(n\)号点以外都没用，就不用再减去那些距离全部小于\(a_j-a_i\)的了。那些相等的可以直接在答案上乘上\(L\).

考虑优化，改变枚举方向，不标志每一个点的最短路是多少，而是枚举最短路为\(i\)的有\(b_i\)，可以节省枚举次数。但是在最后要乘上\((n-2)!\)，因为给每个点定序，但是又要除以所有的\(b_i!\),因为两个点一样就不用再排序了。

#include
const int mod=1e9+7,N=15;
int n,k,l,a[N],s[N],t,jc=1,bit[N];
long long ret,cnt,ans,q,tmp;
void dfs(int x,int y)
{
	if(x>k)
	{
		if(y+2==n||l!=k)
		{
			tmp=1;
			a[t=1]=0;
			for(int i=1;i<=k;i++)
				for(int j=1;j<=s[i];j++)
					a[++t]=i;
			a[++t]=k;
			for(int j=1;j<=n-2-y;j++)
				a[++t]=k+1;
			for(int i=2;i<=n;i++)
			{
				ret=cnt=1;
				for(int j=1;j