Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Christmas Gifts

By fsshakkhor · 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

Discussion

Statistics


100% Solution Ratio

AnachorEarliest, 8M ago

tmwilliamlin168Fastest, 0.1s

AnachorLightest, 131 kB

AnachorShortest, 1267B

Submit

Login to submit

Related Contests