#1236. 连边

连边

Description

有N个点(编号1到N)组成的无向图,已经为你连了M条边。请你再连K条边,使得所有的点的度数都是偶数。求有多少种连的方法。要求你连的K条边中不能有重边,但和已经连好的边可以重。不允许自环的存在。求连边的方法数。我们只关心它模10007的余数。

Format

Input

输入的第一行有三个自然数,分别表示点数N,已经连好的边数M,和你要连的边数K。保证K≤N(N-1)/2 接下来M行每行两个整数x,y,描述了一条连接x和y的边。 30%的数据满足: N≤200 100%的数据满足: N≤1000,M≤N,K≤1000,K≤N(N-1)/2

Output

输出一个整数,表示连边的方法数模10007的余数

Samples

5 1 4
1 2
13

Limitation

【样例说明】 以下是13种连边的方法(只显示你连的边): {(1,2),(1,3),(1,4),(3,4)} {(1,2),(1,3),(1,5),(3,5)} {(1,2),(1,4),(1,5),(4,5)} {(1,2),(2,3),(2,4),(3,4)} {(1,2),(2,3),(2,5),(3,5)} {(1,2),(2,4),(2,5),(4,5)} {(1,2),(3,4),(3,5),(4,5)} {(1,3),(2,4),(3,5),(4,5)} {(1,3),(2,5),(3,4),(4,5)} {(1,4),(2,3),(3,5),(4,5)} {(1,4),(2,5),(3,4),(3,5)} {(1,5),(2,3),(3,4),(4,5)} {(1,5),(2,4),(3,4),(3,5)}

对于20%的数据, 4≤N≤100。对于40%的数据, 4≤N≤5000。对于100%的数据,4≤N≤50000 1≤M≤10 M≤N 所有出现的整数均不超过32位含符号整数。 时间限制:1s