连边

时间限制:20s      空间限制:259MB

题目描述

有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


题目来源

版权所有者:范浩强