Super-Fast Circular Races

A racing club wants to break the record for the total number of tracks (segments) used across several circular races held at the same time. The city has $n$ intersections. Tracks connect intersections; every track is one-way, so it may be driven in one fixed direction only.

The club will hold one or more races. Each race runs around a single closed loop of tracks (a directed cycle), going round and round. For safety, no two races may share a track or an intersection, and no race may pass through the same intersection twice. In other words, the chosen races form a set of vertex-disjoint and edge-disjoint simple directed cycles.

The club wants the total number of tracks used by all races to equal exactly $n$ (the previous record was $n-1$). A single simple directed cycle uses as many tracks as the intersections it visits, so a total of $n$ tracks means every intersection is visited by exactly one race.

Each intersection has at most two outgoing tracks and at most two incoming tracks. No track starts and ends at the same intersection.

Decide whether such an arrangement of races (with total length exactly $n$) exists, and if so, count the number of different arrangements. Print the uppercase word NIE if it is impossible; otherwise print the number of arrangements modulo $10000$.

The first line contains two integers $n$ and $m$ separated by a space ($1 \le n \le 10000$, $1 \le m \le 20000$). Here $n$ is the number of intersections and the target total track length, and $m$ is the number of tracks. Each of the next $m$ lines contains two integers $p$ and $q$ separated by a space, describing a one-way track that leaves intersection $p$ and ends at intersection $q$.

If no arrangement of races with total length $n$ exists, print the single word NIE. Otherwise print one integer: the number of such arrangements modulo $10000$.