[JXOI2012] 奇怪的道路
题目描述
小宇从历史书上了解到一个古老的文明。这个文明在各个方面高度发达,交通方面也不例外。考古学家已经知道,这个文明在全盛时期有 $n$ 座城市,编号为 $1,2,...,n$。$m$ 条道路连接在这些城市之间,每条道路将两个城市连接起来,使得两地的居民可以方便地来往。一对城市之间可能存在多条道路。
据史料记载,这个文明的交通网络满足两个奇怪的特征。
1. 这个文明崇拜数字 $k$,对于任何一条道路,设它连接的两个城市分别为 $u$ 和 $v$,则必定满足 $1 \le \left\vert {u-v}\right\vert \le k$。
2. 任何一个城市都与恰好偶数条道路相连( $0$ 也被认为是偶数)。
不过,由于时间过于久远,具体的交通网络我们已经无法得知了。小宇很好奇这 $n$ 个城市之间究竟有多少种可能的连接方法,于是她向你求助。
两种可能的连接方法不同当且仅当存在一对城市,它们间的道路数在两种方法中不同。
在交通网络中,有可能存在两个城市无法互相到达。
方法数可能很大,你只需要输出方法数模 $10^9 + 7$ 后的结果。
输入输出格式
输入格式
输入共一行,有三个整数 $n,m,k$。
输出格式
输出一个整数,表示方案数模 $10^9 + 7$ 后的结果。
输入输出样例
输入样例 #1
3 4 1
输出样例 #1
3
输入样例 #2
4 3 3
输出样例 #2
4
说明
#### 数据规模与约定
- 对于 $100\%$ 的数据,满足 $1 \le n,m \le 30$,$1 \le k \le 8$。