Sister Ports

ACM is an island nation in the shape of a regular $n$-gon. There are ports at the $n$ vertices, numbered 1 to $n$ clockwise starting from one vertex. Ports are treated as points.

ACM has two kinds of roads.

1. Roads connecting adjacent ports Every pair of adjacent ports is connected by a road. That is, there is a road between ports whose numbers differ by 1, and between port 1 and port $n$. There are $n$ roads of this kind.
2. Roads passing through the interior of the island Some pairs of non-adjacent ports are also connected by roads. There are $m$ roads of this kind, and road $i$ connects port $a_i$ and port $b_i$.

Roads are treated as line segments. In ACM, no two roads share a point other than an endpoint.

Figure G-1: An example of ports and roads

To prepare for accidents at ports, ACM decided to assign a sister port to every port so that any two ports can help each other at any time. Every port has exactly one sister port, and if port $a$ is the sister port of port $b$, then port $b$ is also the sister port of port $a$. That is, the $n$ ports are divided into $n/2$ pairs of distinct ports. ACM further decided that there must be a road between sister ports.

Your job, as an excellent programmer living in ACM, is to write a program that computes the total number of ways to assign sister ports to all ports.

Figure G-2: Examples of assignments of sister ports (roads between sister ports are shown as thick red lines)

The input consists of one or more data sets. Each data set has the following format.

n m
a1 b1
...
am bm

The first line contains two positive integers $n$ and $m$, which are the number of ports in ACM and the number of roads of kind 2. The $i$-th of the following $m$ lines contains two integers $a_i$ and $b_i$, meaning that road $i$ connects ports $a_i$ and $b_i$.

No two roads share a point other than an endpoint. The numbers have the following ranges.

• $3 \le n \le 50{,}000$
• $0 \le m \le 50{,}000$
• $1 \le a_i, b_i \le n$

The end of the input is marked by a line containing two zeros.

For each data set, output the total number of ways to assign sister ports modulo $1000003$. If no valid assignment of sister ports exists, output 0.