きたまさ君は大学でさまざまな変換について研究している。最近、きたまさ君が興味を持っている変換は次のようなものである。 N+1個の整数 a0, ..., aN を固定し、整数 z を入力とする。また P を素数とする。
t = ( aNzN + aN-1zN-1 + ... + a2z2 + a1z + a0 ) mod P
きたまさ君はこの変換によって t = 0 になってしまう z がいくつもあることに気がついた。 そこで、きたまさ君は友人でありスーパープログラマーでもあるあなたに、変換後に t = 0 になる z が 0〜P-1 にいくつあるかを計算してもらうことにした。
入力は次の形式で与えられる。
N P a0 a1 ... aN
入力の1行目には整数Nと素数Pがスペース文字で区切られて与えられる。これらは、問題文で与えられたとおりである。 0 ≤ N ≤ 100, 2 ≤ P ≤ 109 を満たす。
次の1行には a0〜aN がスペース文字で区切られて与えられる。これらは |ai| ≤ 109 を満たす整数である。また aN ≠ 0 である。
変換後に0になるような z (0 ≤ z < P) の個数を出力せよ。
上記入力形式で複数のデータセットが与えられます。各データセットに対して上記出力形式で出力を行うプログラムを作成して下さい。
N, P がともに 0 のとき入力の終わりを示します。
2 3 1 2 1 2 3 1 2 6 0 0
1 1