Última estrada
Uma rede tem cidades e estradas não direcionadas. As estradas foram inauguradas uma por dia, nos dias , em alguma ordem. Cada cidade registrou apenas o dia da inauguração da última estrada incidente nela. Uma cidade sem estradas registrou .
A rede e os registros são conhecidos. Conte quantas ordens de inauguração são compatíveis com todos os registros, módulo . Duas ordens são diferentes se alguma estrada foi inaugurada em dias diferentes.
Input
A primeira linha contém e (, ). A segunda contém inteiros (). Cada uma das próximas linhas contém e (, ), descrevendo uma estrada. Não há estradas repetidas. A rede pode ser desconexa. Os registros não são necessariamente compatíveis com a rede.
Output
Imprima a quantidade de ordens compatíveis, módulo . Se , há uma única ordem, a ordem vazia.
Samples
Sample 1
Input
3 3 3 3 2 1 2 1 3 2 3
Output
2
A estrada entre e deve ser a última. As outras duas podem ser inauguradas em qualquer ordem.