题目描述

在电影《超能陆战队》中，小宏可以使用他的微型机器人组合成各种各样的形状。

现在他用他的微型机器人拼成了一个大玩具给小朋友们玩。为了更加美观，他决定给玩具染色。

小宏的玩具由 n 个球型的端点和 m 段连接这些端点之间的边组成。下图给出了一个由 5 个球型端点和 4 条边组成的玩具，看上去很像一个分子的球棍模型。

由于小宏的微型机器人很灵活，这些球型端点可以在空间中任意移动，同时连接相邻两个球型端点的边可以任意的伸缩，这样一个玩具可以变换出不同的形状。在变换的过程中，边不会增加，也不会减少。

小宏想给他的玩具染上不超过 k 种颜色，这样玩具看上去会不一样。如果通过变换可以使得玩具变成完全相同的颜色模式，则认为是本质相同的染色。现在小宏想知道，可能有多少种本质不同的染色。

输入描述

输入的第一行包含三个整数 n,m,k，分别表示小宏的玩具上的端点数、边数和小宏可能使用的颜色数。端点从 1 到 n 编号。

接下来 m 行每行两个整数 a,b，表示第 a 个端点和第 b 个端点之间有一条边。输入保证不会出现两条相同的边。

其中，1≤n≤10,1≤m≤45,1≤k≤30。

输出描述

输出一行，表示本质不同的染色的方案数。由于方案数可能很多，请输入方案数除 10007 的余数。

输入输出样例

示例

输入

3 2 2
1 2
3 2

输出

6

样例说明

令 (a,b,c) 表示第一个端点染成 a，第二个端点染成 b，第三个端点染成 c，则下面 6 种本质不同的染色：(1,1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 2), (2, 2, 2)。

而(2, 1, 1)与(1, 1, 2)是本质相同的，(2, 2, 1)与(1, 2, 2)是本质相同的。