Izua Dictionary

Time Limit : 8 sec, Memory Limit : 65536 KB

イヅア国語辞典

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

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

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

入力

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

N
R
s1 t1
s2 t2
:
sR tR

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

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

出力

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

入力例

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

出力例

3
4

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


Source: PC Koshien 2012 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2012-11-10
http://www.pref.fukushima.jp/pc-concours/