SPOJ Brasil

Um grupo de N crianças decidiu brincar de rouba bandeira. Para isso, elas precisam se separar em dois times com a mesma quantidade de crianças. Porém, algumas delas são muito amigas e querem estar no mesmo time. Por outro lado, outras são inimigas e não querem estar no mesmo time. Determine o número de formas de dividir os times satisfazendo todas essas restrições. Duas formas de dividir as crianças em times são consideradas diferentes se e somente se existe um par de crianças que são companheiras em uma das formas e adversárias na outra. Como a resposta pode ser muito grande, calcule-a mod 1.000.000.007.

Entrada

Há múltiplos casos de teste.

A primeira linha de cada caso de teste contém três inteiros N, A e I (1 ≤ N ≤ 1000, 0 ≤ A, I ≤ (n·(n-1))/2), onde N é o número de crianças, A é o número de relações de amizade e I é o número de relações de inimizade. A seguir, A linhas descrevem as relações de amizade e I linhas descrevem as relações de inimizade. Uma relação de amizade/inimizade é representada por um par de inteiros (p, q), tal que 1 ≤ p, q ≤ N, indicando que a relação existe entre as crianças p e q.

A entrada termina quando N=A=I=0.

Saída

Para cada caso de teste, imprima uma linha contendo um único inteiro que representa o número de formas de dividir os times mod (10⁹ + 7).

Exemplos

Entrada:
2 0 0
4 0 0
4 1 2
1 2
1 3
2 4
3 0 0
0 0 0

Saída:
1
3
1
0