English text is not available in this practice contest.

ACM 国は正 n 角形の島国である． n 個の角に港があり，ある角の港から時計回りに 1 から n までの番号が順番に付いている． 港は点とみなす．

ACM 国には，二種類の道路がある．

1. 隣り合う港を繋ぐ道路 全ての隣接する港は道路で接続されている．すなわち，番号の差が 1 である港同士および港 1 と港 n の間に道路がある．この種類の道路は n 本ある．
2. 島の内部を通る道路 一部の隣接しない港の間も，道路で接続されている．この種類の道路は m 本あり，道路 i は港 a_i と港 b_i を接続する．

道路は線分とみなす．ACM 国では，任意の 2 つの道路は端点以外で共有点を持たない．

図 G-1: 港と道路の例

ACM 国は，港に事故が起きた時などに備えるため，全ての港について姉妹港を決め，いつでも互いを補助できるよう準備させることにした． 全ての港について姉妹港は 1 つで，港 a が港 b の姉妹港であるとき，港 b も港 a の姉妹港である． すなわち，n 個の港から，港が重複しない n/2 個のペアを作る． このとき，ACM 国は，姉妹港の間には必ず道がなければならないとすることにした．

ACM 国に住む優秀なプログラマーであるあなたの仕事は， 全港に対する姉妹港の選び方の総数を計算するプログラムを作成することである．

図 G-2: 姉妹港の選び方の例（姉妹港同士の間の道路を赤色太線で表示している）

入力は1つ以上のデータセットからなる．1つのデータセットは次の形式をしている．

n m
a₁ b₁
...
a_m b_m

先頭行は 2 つの正の整数 n, m からなり， それぞれ ACM 国の港の数および種類 2 の道路の数を表す． 続く m 行の i 行目は 2 個の整数 a_i, b_i からなり， 道路 i が港 a_i, b_i を結ぶことを表す．

任意の 2 つの道路は端点以外で共有点を持たない．また，これらの数は以下の範囲の値をとる．

• 3 ≤ n ≤ 50,000
• 0 ≤ m ≤ 50,000
• 1 ≤ a_i, b_i ≤ n

入力の終わりはふたつのゼロを含む行で表される．

各データセットについて， 姉妹港の選び方の総数を 1000003 で割った余りを出力せよ． 適切な姉妹港の選び方が存在しない場合は 0 を出力せよ．

6 1
1 4
8 3
1 6
1 5
2 5
12 3
3 10
4 9
6 9
3 0
0 0

3
5
7
0