It's Christmas time! It's the time when Santa brings gift for the children. This year Santa has $K$ types of gifts. Remember that, he has infinite supply for each type of gift.
There are $N$ children who are waiting for Santa's gifts. Santa will give exactly one gift to each of the child. This gift can be of any type. But there is a small restriction. No two friend should get same type of gift. Santa has the list of $M$ pairs of children who are friends.
Now Santa wants to know, how many different ways he can distribute the gifts among the children. As the number of such distributions can be huge, print it modulo $10^9 + 7$.
Two distributions are considered different if there exist a child who gets different type of gift in those distribution.
Input
The first line will contain an integer $T (1 ≤ T ≤ 50)$, denoting the number of test cases.
Each test case starts with three integers $N (1 ≤ N ≤ 1000)$, $M (0 ≤ M ≤ 15)$ and $K (1 ≤ K ≤ 10^9)$, denoting the number of children, number of pair of friends and number of type of gifts.
Each of next $M$ lines contain two integers $A,B (1 ≤ A,B ≤ N$ and $ A$ ≠ $B)$, denoting that $A$ and $B$ are friends. All the given $(A,B)$ pair will be distinct. Also if the input contains $(A,B)$ pair, it will not contain $(B,A)$ pair.
Output
For each test case, print the number of ways to distribute the gifts modulo $10^9 + 7$.
Sample
| Input | Output |
|---|---|
3 4 3 2 1 2 2 3 3 4 3 3 3 1 2 2 3 1 3 3 3 4 1 2 2 3 1 3 | 2 6 24 |
Let us number the gifts from 1 to K. Case 1: There are only 2 ways to distribute the gifts.
Case 2: All the 3 children must get different type of gifts.
| |
