Problem J: 多項式の解の個数

きたまさ君は大学でさまざまな変換について研究している。最近、きたまさ君が興味を持っている変換は次のようなものである。 N+1個の整数 a₀, ..., a_N を固定し、整数 z を入力とする。また P を素数とする。

t = ( a_Nz^N + a_N-1z^N-1 + ... + a₂z² + a₁z + a₀ ) mod P

きたまさ君はこの変換によって t = 0 になってしまう z がいくつもあることに気がついた。 そこで、きたまさ君は友人でありスーパープログラマーでもあるあなたに、変換後に t = 0 になる z が 0〜P-1 にいくつあるかを計算してもらうことにした。

Input

入力は次の形式で与えられる。

N P
a0 a1 ... aN 

入力の1行目には整数Nと素数Pがスペース文字で区切られて与えられる。これらは、問題文で与えられたとおりである。 0 ≤ N ≤ 100, 2 ≤ P ≤ 10⁹ を満たす。

次の1行には a₀〜a_N がスペース文字で区切られて与えられる。これらは |a_i| ≤ 10⁹ を満たす整数である。また a_N ≠ 0 である。

Output

変換後に0になるような z (0 ≤ z < P) の個数を出力せよ。

Sample Input 1

2 3
1 2 1

Output for Sample Input 1

1

Sample Input 2

2 3
1 2 6

Output for Sample Input 2

1