자매 항구

ACM 나라는 정$n$각형 모양의 섬나라이다. $n$개의 꼭짓점에 항구가 있고, 어떤 꼭짓점의 항구부터 시계 방향으로 1부터 $n$까지의 번호가 차례대로 붙어 있다. 항구는 점으로 본다.

ACM 나라에는 두 종류의 도로가 있다.

1. 인접한 항구를 잇는 도로 모든 인접한 항구는 도로로 연결되어 있다. 즉, 번호 차이가 1인 항구끼리, 그리고 항구 1과 항구 $n$ 사이에 도로가 있다. 이 종류의 도로는 $n$개 있다.
2. 섬 내부를 지나는 도로 일부 인접하지 않은 항구 사이도 도로로 연결되어 있다. 이 종류의 도로는 $m$개 있으며, 도로 $i$는 항구 $a_i$와 항구 $b_i$를 연결한다.

도로는 선분으로 본다. ACM 나라에서는 임의의 두 도로가 끝점이 아닌 곳에서 만나지 않는다.

그림 G-1: 항구와 도로의 예

ACM 나라는 항구에 사고가 났을 때 등에 대비해 모든 항구에 대해 자매 항구를 정하고, 언제든 서로를 돕도록 준비시키기로 했다. 모든 항구의 자매 항구는 하나이고, 항구 $a$가 항구 $b$의 자매 항구이면 항구 $b$도 항구 $a$의 자매 항구이다. 즉, $n$개의 항구에서 항구가 겹치지 않는 $n/2$개의 쌍을 만든다. 이때 ACM 나라는 자매 항구 사이에는 반드시 도로가 있어야 한다고 정했다.

ACM 나라에 사는 뛰어난 프로그래머인 당신의 일은 모든 항구에 대한 자매 항구를 정하는 방법의 총수를 계산하는 프로그램을 만드는 것이다.

그림 G-2: 자매 항구를 정하는 방법의 예 (자매 항구 사이의 도로를 빨간 굵은 선으로 표시했다)

입력은 하나 이상의 데이터 세트로 이루어진다. 하나의 데이터 세트는 다음 형식이다.

n m
a1 b1
...
am bm

첫 줄은 두 양의 정수 $n$, $m$으로 이루어지며, 각각 ACM 나라의 항구 수와 종류 2 도로의 수를 나타낸다. 이어지는 $m$개의 줄 중 $i$번째 줄은 두 정수 $a_i$, $b_i$로 이루어지며, 도로 $i$가 항구 $a_i$, $b_i$를 잇는다는 뜻이다.

임의의 두 도로는 끝점이 아닌 곳에서 만나지 않는다. 또한 이 수들은 다음 범위의 값을 가진다.

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

입력의 끝은 두 개의 0을 포함하는 줄로 나타낸다.

각 데이터 세트에 대해 자매 항구를 정하는 방법의 총수를 $1000003$으로 나눈 나머지를 출력하라. 적절한 자매 항구의 선택이 존재하지 않으면 0을 출력하라.