题目描述
魔法宫殿的最深处藏着一把万能权杖，为这个国家提供了强大的军事力量，然而有天却被一个等级略低的小法师误用，导致强大的法术失控，并形成了一个怪异的法阵保护着法杖。国家少了一件圣器，在战火纷飞的年代国力也逐渐衰退，历代国王们不惜一切代价和奖赏，吸引人们来破解法阵，可惜百年来无人能破。现在你穿越来到了宫殿，这个法阵就摆在你面前，它由许多魔法球连接而成，你可以看成一张联通的无向图，由于这个世界的元素是平衡的，相邻的魔法球如果具有相同的元素，就会发出元素之力伤害周围的人，当然，问题还不止这么简单，你不仅仅要使相邻魔法球之间的元素互不相同，还得知道对于K种元素，有多少种方案可以满足这个条件，听完国王的描述，你一言不发，掏出笔记本，打开编译器……
输入
第一行输入三个正整数N, M, K（N <= 50, M <= 1000, 2<=K <= 4），分别表示点的个数，边的个数，元素数量，第2行到第1 + M行，每行两个正整数U, V（U <= N, V <= N且U != V）， 表示U到V有一条双向边，图保证联通。
输出
一个整数，表示用最多K种元素赋予魔法球的方案数，答案对1e9 + 7取模
4 5 4
1 4
1 2
1 3
3 4
3 2