Christmas Gifts

fsshakkhor The Tough Winter Spar, 20...
Limits 1s, 512 MB

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

InputOutput
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.

  • Type 1 to child 1, type 2 to child 2, type 1 to child 3 and type 2 to child 4.
  • Type 2 to child 1, type 1 to child 2, type 2 to child 3 and type 1 to child 4.

Case 2: All the 3 children must get different type of gifts.

  • type 1, type 2, type 3 (means child 1,2,3 gets type 1,2,3 respectively)
  • type 1, type 3, type 2
  • type 2, type 1, type 3
  • type 2, type 3, type 1
  • type 3, type 1, type 2
  • type 3, type 2, type 1

Submit

Login to submit.

Statistics

100% Solution Ratio
AnachorEarliest, Dec '19
tmwilliamlin168Fastest, 0.1s
AnachorLightest, 131 kB
AnachorShortest, 1267B
Toph uses cookies. By continuing you agree to our Cookie Policy.