Problem 1060 - USTC Online Judge

Rank

Problem 1060

Brand New Game

Time Limit: 1000ms
Memory Limit: 65536kb

Description

Alice and Bob are fond of a new interesting game. In this game, they play by turns in a Directed Acyclic Graph (DAG). Every node of the graph is assigned a non-negative integer at the beginning. Each round a player must choose a node having a positive integer and transfer 1 to every of its succeeding nodes.Its integer decreases by 1 and all its succeeding node’s integer increases by 1. If the node doesn't have any succeeding nodes, only decrease the node's integer. Who can not find such a node to transfer will lose. The integer whose number is 0 has at least 1 succeeding node.
Before playing the game, they come to an agreement about the integer assignment. Alice plays first. To be fair, Bob is responsible for assigning an integer to each node. But there is a constraint: the sum of all integers must be a predetermined value that they both agree.
Now, given the sum, Alice wonders how many distinct assignments which will prevent her from winning. Two assignments are different if there is one node assigned different integers in the two assignments.
Alice and Bob are so smart that they can always find the best strategy.

Input

The first line is a number indicating the number of test cases.
The first line of each test case includes three number N, M and S (2<=N<=100, 1<=M<=10000, 1<= S <=10000) indicating the number of nodes, the number of edges and the sum of all integers respectively. Nodes are numbered by 0…N-1.
The following M lines each have two integers, u and v, indicating an edge from u to v (0 <= u, v <N).You can assume there is no cycle in the graph.

Output

For each test case, output a single integer indicating how many distinct assignments in which Alice can NOT win. Because it can be very large, you should output the remainder divided by 1,000,000,007.

Sample Input

Sample Output

2
10
12

Source

yuzhou627

[Submit|Status|Discuss|Add to bookmark]