초고속 원형 경주

한 경주 클럽이 동시에 열리는 여러 원형 경주에서 사용하는 트랙(구간)의 총 개수 기록을 깨려고 합니다. 도시에는 교차로가 $n$개 있습니다. 트랙은 교차로 사이를 잇는 일방통행 도로이며, 정해진 한 방향으로만 달릴 수 있습니다.

클럽은 하나 이상의 경주를 개최합니다. 각 경주는 트랙들이 이루는 하나의 닫힌 순환(방향 사이클)을 따라 돌고 돕니다. 안전을 위해 서로 다른 두 경주는 같은 트랙이나 같은 교차로를 공유할 수 없고, 한 경주는 같은 교차로를 두 번 지날 수 없습니다. 즉, 선택된 경주들은 서로 정점과 간선이 겹치지 않는 단순 방향 사이클들의 모임입니다.

클럽은 모든 경주가 사용하는 트랙의 총 개수가 정확히 $n$이 되기를 원합니다(직전 기록은 $n-1$이었습니다). 단순 방향 사이클 하나는 지나는 교차로의 수와 같은 수의 트랙을 사용하므로, 트랙 총합이 $n$이 되려면 모든 교차로가 정확히 하나의 경주에 의해 방문되어야 합니다.

각 교차로에서 나가는 트랙은 최대 두 개, 들어오는 트랙도 최대 두 개입니다. 어떤 트랙도 같은 교차로에서 시작해 그 교차로에서 끝나지 않습니다.

이러한 경주 배치(총 길이가 정확히 $n$)가 가능한지 판단하고, 가능하다면 서로 다른 배치의 개수를 구하세요. 불가능하면 대문자 단어 NIE를, 가능하면 배치의 개수를 $10000$으로 나눈 나머지를 출력하세요.

첫째 줄에 두 정수 $n$과 $m$이 공백으로 구분되어 주어집니다 ($1 \le n \le 10000$, $1 \le m \le 20000$). $n$은 교차로의 수이자 목표로 하는 트랙의 총 길이이고, $m$은 트랙의 수입니다. 이어지는 $m$개의 줄에는 각 트랙을 나타내는 두 정수 $p$와 $q$가 공백으로 구분되어 주어지며, 이는 교차로 $p$에서 출발해 교차로 $q$에서 끝나는 일방통행 트랙을 뜻합니다.

총 길이가 $n$인 경주를 배치할 수 없으면 한 단어 NIE를 출력합니다. 배치할 수 있으면 그러한 배치의 개수를 $10000$으로 나눈 나머지를 정수 하나로 출력합니다.