题目描述

小宇从历史书上了解到一个古老的文明。这个文明在各个方面高度发达，交通方面也不例外。考古学家已经知道，这个文明在全盛时期有 $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$ 后的结果。

3 4 1

3

4 3 3

4

提示

数据规模与约定

• 对于 $100\%$ 的数据，满足 $1 \le n,m \le 30$，$1 \le k \le 8$。