该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

现在有n个人要排成一列，编号为1→n。但由于一些不明原因的关系，人与人之间可能存在一些矛盾关系，具体有m条矛盾关系(u,v)，表示编号为u的人想要排在编号为v的人前面。要使得队伍和谐，最多不能违背k条矛盾关系（即不能有超过k条矛盾关系(u,v)，满足最后v排在了u前面）。问有多少合法的排列。答案对〖10〗^9+7取模。

Input Format

输入文件名为count.in。 第一行包括三个整数n,m,k。 接下来m行，每行两个整数u,v，描述一个矛盾关系(u,v)。 保证不存在两对矛盾关系(u,v),(x,y)，使得u=x且v=y。

Output Format

输出文件名为count.out。 输出包括一行表示合法的排列数。

Sample

【输入样例1】

4 2 1
1 3
4 2

【输出样例1】

18

【输入样例2】

10 12 3
2 6
6 10
1 7
4 1
6 1
2 4
7 6
1 4
10 4
10 9
5 9
8 10

【输出样例2】

123120

Hint

对于30%的数据，n≤10;

对于60%的数据，n≤15;

对应100%的数据，n,k≤20,m≤n×(n-1)，保证矛盾关系不重复。