Migrated from Lutece 1159 Easy problem ( trust me

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given a Directed acyclic graph (DAG) with $N$ ($1 \leq N \leq 20$) nodes and $M$ edges.

There is a set $S$ which contains $K$ ($1 \leq K \leq 10^9$) distinct integers. Each node has a set that contains some distinct integers (possibly empty).

The Directed acyclic graph is legal only if the set of each node is a subset of $S$ and is a subset of nodes which can directly arrive it.

You are supposed to calculate how many kinds of graphs are legal. Calculate the answer mod $10^9+7$.

Two graphs are considered different if there is at least one node in two graphs has different set.

See Hint for more understanding.

Input

The first line contains three integers $N$ ($1 \leq N \leq 20$) and $M$, $K$ ($1 \leq K \leq 10^9$).

The second $M$ lines contains two integers $a$ and $b$ ($1 \leq a , b \leq N$), representing that there is a direct edge from $a$ to $b$

It is guaranteed that the given graph is a simple graph without multiple edges.

Output

Output the answer mod $10^9+7$.

Samples

4 4 2
1 2
2 3
1 3
3 4

25

Note

Let consider the following sample.

There are 2 nodes and 1 edges that is 1--->2. And $K$=2, that means $S$ contains 2 integers.

the set of node 2 must be a subset of node 1.

the set of node1 must be a subset of node $S$

if S={1, 2}, then , let S1 be the set of node 1, S2 be the set of node2

S1={1 ,2} S2={1, 2}

S1={1 ,2} S2={ 1 }

S1={1 ,2} S2={ 2 }

S1={1 ,2} S2={ }

S1={ 1 } S2={ 1 }

S1={ 1 } S2={ }

S1={ 2 } S2={ 2 }

S1={ 2 } S2={ 0 }

S1={ } S2={ }

Therefore ,the answer is 9. There are 9 legal DAGs.

Resources

2015 UESTC ACM Summer Training Team Selection (4)