分数: 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