イヅア国語辞典

あなたはイヅア国の公用語であるイヅア語の国語辞典と、イヅア語のアルファベット（文字の一覧表） を手に入れました。イヅア語のアルファベットにはN 種類の文字があります。イヅア語の国語辞典に現れる単語の順番は、イヅア語のアルファベット順に並んでいます。

辞典を見ると、載っているどの単語もN 文字で、しかも、N 種類の文字をひとつずつ含んでいることがわかりました。さらに調べてみると、辞典にはN 種類の文字の可能な並び方がすべて書かれていることを発見しました。

この発見から、あなたはある単語が辞典の何番目に出てくるかわかるようになりました。この知識を利用してイヅア国の人を驚かせてみましょう。まず、N 種類の文字をひとつずつアルファベット順に並べます。次に、任意の２文字の順番を入れ替える操作を R 回繰り返してもらいます。あなたは、出来上がった単語がイヅア国語辞典の何番目に出てくるか当てて見せます。そのための準備として、国語辞典中の単語の場所を求めるプログラムを作成してください。ただし、アルファベット順で最初の単語を 0 番目の単語とします。

入力

入力は複数のデータセットからなる。入力の終わりはゼロ１つの行で示される。各データセットは以下の形式で与えられる。

N
R
s1 t1
s2 t2
:
sR tR

１行目にアルファベットを構成する文字の数 N (1 ≤ N ≤ 100000) が与えられ、２行目に文字を入れ替えてもらう回数 R (0 ≤ R ≤ 50) が与えられる。続く R 行に、入れ替えられる文字の位置の組が与えられる。s_i と t_i (1 ≤ s_i < t_i ≤ N) は、先頭から数えて s_i 番目と t_i 番目の文字を i 回目に入れ替えることを表す。s_i と t_i は１つの空白で区切られている。

データセットの数は100 を超えない。

出力

データセットごとに、入れ替えが終わった時点で得られた単語が国語辞典の何番目に現れるかを示す数を１行に出力する。ただし、出力すべき値は非常に大きくなりうるので、代わりに 1,000,000,007 で割った余りを出力する。

入力例

3
2
1 2
2 3
4
2
2 3
2 4
0

出力例

3
4

入出力例の最初のデータセットについて説明する。説明のため、アルファベットは小さい方から順番に、'A', 'B', 'C' の３文字からなるとする。これらの文字をアルファベット順に並べると "ABC" という文字列が得られる。この文字列の１番目の文字 'A' と２番目の文字 'B' を入れ替えると、"BAC" という文字列が得られる。次に、得られた文字列の２番目の文字 'A' と３番目の文字 'C' を入れ替えると、単語 "BCA" が得られる。辞典には、先頭から順に "ABC", "ACB", "BAC", "BCA", "CAB", "CBA" の６種類の単語が載っている。"BCA" はこの中で３番目（最初の"ABC"が０番目であることに注意）に現れるので、3 を 1,000,000,007 で割った余りである 3 が答えになる。