有一天牛牛来到了一片新大陆，大陆上有n个村庄，编号为1到N,一开始他们两两之间没有道路连接，牛牛准备在他们之间建立M条双向的通路，每一条通路连接两个村庄
修建道路的规则如下
- 只允许在编号之差小于等于K的村庄之间建立道路，允许两个村庄之间建立多条道路
- 每个村庄一定要与偶数个村庄相邻（包括0）
请问一共有多少种不同的道路构造的方案,答案对1e9+7取模
输入描述:
输入一行，包含三个整数N,M,K
1 ≤ N ≤ 30
0 ≤ M ≤ 30
1 ≤ K ≤ 8
输出描述:
输出一个整数
备注:
子任务1： n <= 5
子任务2： n <= 15
子任务3： n <= 130