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 KK types of gifts. Remember that, he has infinite supply for each type of gift.

There are NN 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 MM 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 109+710^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(1T50)T (1 ≤ T ≤ 50), denoting the number of test cases.

Each test case starts with three integers N(1N1000)N (1 ≤ N ≤ 1000), M(0M15)M (0 ≤ M ≤ 15) and K(1K109)K (1 ≤ K ≤ 10^9), denoting the number of children, number of pair of friends and number of type of gifts.

Each of next MM lines contain two integers A,B(1A,BNA,B (1 ≤ A,B ≤ N and A AB)B), denoting that AA and BB are friends. All the given (A,B)(A,B) pair will be distinct. Also if the input contains (A,B)(A,B) pair, it will not contain (B,A)(B,A) pair.

Output

For each test case, print the number of ways to distribute the gifts modulo 109+710^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, Dec '19

tmwilliamlin168Fastest, 0.1s

AnachorLightest, 131 kB

AnachorShortest, 1267B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.