You are given a small undirected graph with n vertices (numbered 1..n) and m edges, and an integer k. A proper k-coloring assigns each vertex one of k colors (numbered 1..k) such that every edge connects two vertices of different colors.

Count the number of distinct proper k-colorings of the graph. Since this count can be large, print it modulo 1,000,000,007.

Input format

Line 1: three integers n, m, and k. Next m lines: two integers u v (1-indexed) — an undirected edge between vertex u and vertex v.

Output format

A single integer: the number of proper k-colorings, modulo 1,000,000,007.

Constraints

• 1 ≤ n ≤ 7
• 0 ≤ m ≤ n*(n-1)/2, with no self-loops and no duplicate edges
• 1 ≤ k ≤ 5

3 3 3
1 2
1 3
2 3

6

2 0 2

4