Practice on Toph
Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
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.
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.
For each test case, print the number of ways to distribute the gifts modulo $10^9 + 7$
.
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.

100% Solution Ratio
AnachorEarliest,
tmwilliamlin168Fastest, 0.1s
AnachorLightest, 131 kB
AnachorShortest, 1267B
Login to submit