Problem D: 古代通信网络

Problem D: 古代通信网络

Time Limit: 1 Sec  Memory Limit: 160 MB
Submit: 23  Solved: 5
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI在研究一种神秘的古代通信网络。这个网络由n个节点(编号为1,2,...,n)和m条通信线路组成。每条通信线路连接两个节点,使得它们之间可以进行数据传输。一对节点之间可能存在多条通信线路。
据研究,这个通信网络具有以下两个特性:
  1. 对于任何一条通信线路,连接的两个节点u和v满足1 ≤ |u - v| ≤ k。
  2. 每个节点恰好与偶数条通信线路相连(0也被认为是偶数)。
PIPI想知道,满足上述条件的通信网络有多少种不同的构建方式。两种构建方式不同当且仅当存在一对节点,它们之间的通信线路数量不同。
请计算满足条件的通信网络的方案数,并对10^9+7取模。

Input

输入一行三个整数n, m, k。

Output

输出一个整数,表示方案数模10^9+7的结果。

Sample Input

3 4 1

Sample Output

3

HINT

对于100%的数据,1 ≤ n, m ≤ 30,1 ≤ k ≤ 8。