← 返回题目列表

AtCoder · arc062_d

F. 使用 AtCoDeer 绘制图形

中文机器翻译题面 查看原题

分数: 1300 点

问题陈述

有一天,鹿 AtCoDeer 发现了一个简单的图(即没有自环和多条边的图),其中 N 顶点和 M 边缘,并把它带回家。 顶点已编号 1 通过 N 且相互可区分,且边由下式表示 (a_i,b_i) (1≦i≦M).

他正在用其中一个绘制图中的每条边 K 他的油漆罐的颜色。由于他有足够的颜料供应,同一种颜色可以用来画多个边缘。

该图由特殊材料制成,具有奇怪的特性。他可以选择一个简单的循环(即没有重复顶点的循环),并沿着所选循环执行颜色的循环移位。更正式地说,让 e_1, e_2, ..., e_a 是沿着一个循环按顺序排列的边,那么他可以同时执行以下操作:绘制 e_2 当前颜色 e_1,油漆 e_3 当前颜色 e_2, ...,油漆 e_a 当前颜色 e_{a-1}和油漆 e_1 当前颜色 e_{a}.

图 1:循环移位的示例

绘制边缘的两种方法, A 和 B,如果 A 可以转化为 B 通过执行有限次数的循环移位。求出绘制边缘的方法数。由于这个数字可能非常大,因此打印答案模数 10^9+7.

约束

  • 1≦N≦50
  • 1≦M≦100
  • 1≦K≦100
  • 1≦a_i,b_i≦N (1≦i≦M)
  • 该图既没有自环也没有多重边。

输入

输入由标准输入按以下格式给出:

N M K
a_1 b_1
a_2 b_2
:
a_M b_M

输出

打印绘制边缘的方式数,模数 10^9+7.


示例输入 1

4 4 2
1 2
2 3
3 1
3 4

示例输出 1

8

示例输入 2

5 2 3
1 2
4 5

示例输出 2

9

示例输入 3

11 12 48
3 1
8 2
4 9
5 4
1 6
2 9
8 3
10 8
4 10
8 6
11 7
1 8

示例输出 3

569519295