#2169. 连边

题目描述

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

输入格式

输入的第一行有三个自然数，分别表示点数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

输出格式

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

样例

样例输入

5 1 4  

1 2

样例输出

13  

【样例说明】  

以下是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