東京大学合格を目指す高校生のきたまさ君は入試問題に飽きてしまった。そこで、きたまさ君は入学前に大学で学ぶことの予習をしておこうと考えた。
きたまさ君は東京大学の生協に行き、教科書コーナーで面白そうな本を探すことにした。 様々な本のなかで、きたまさ君は計算量理論の本に興味を持ち、その本を読んでみることにした。
その本には次のようなことが書かれていた。 「グラフの彩色数を求める問題はNP困難である」
ところが、きたまさ君はグラフの彩色数を多項式時間で計算するアルゴリズムを思いついてしまった！これを用いるとP=NPであることが証明できる！！
きたまさ君はこの大発見を論文にしようと思ったのだが、残念ながらきたまさ君は日本語も英語もあまり得意ではないので、分かりやすくアルゴリズムを解説することができなかった。 そこで、きたまさ君は実際にこのアルゴリズムを実装して、無向グラフの彩色数を求めるプログラムを作り、それを公開することによって自分の正しさを示そうと考えた。 ちなみに、彩色数とは、グラフの頂点に 1～K の番号を振ったとき、辺で結ばれた頂点同士を全て異なる番号にできるような最小の K のことである。
また、多項式時間で動作していると主張するためには、グラフはとても大きくなければならないだろうときたまさ君は考え、次のようにして巨大グラフを生成することにした。
1. N 個の頂点v0～vN -1を作る。
2. 線形合同法により長さ 2M の擬似乱数列 x を作成する。 具体的には次のような漸化式により、数列 x0～x2M -1 を作成する。
xi +1 = a xi + b mod N
3. i = 0, 1, ..., M -1に対して、x2i≠ x2i +1ならば、x2i番とx2i +1番の頂点の間に辺を張る。
入力は以下のような形式で与えられる。
N M x0 a b
1 ≤ N ≤ 10000, 1 ≤ M ≤ 1000000, 0 ≤ x0, a, b < N
N, M, x0, a, b の意味は問題文中の巨大グラフ生成アルゴリズムの説明を参照せよ。
入力を用いて生成した巨大グラフの彩色数を一行に出力せよ。
6 4 1 4 2
3