\(A\) の要素は \(M\) で割ったあまりを考えます。

初期状態で操作可能な \(i\) が存在しない場合、答えは No です。

\(A\) の要素の総和が \(M\) の倍数である場合、どのように操作しても最終的に \(M\) の倍数が作られます。答えは No です。

以下ではそれ以外の場合を考えます。

初期状態で操作可能な \(i\) が存在します。操作を行い、操作可能な\(i\)が1つ以上存在する状態を最後まで維持できれば良いです。これは必ず可能です。

操作不可能な \(i\) が存在するとき

\(i=x\) が操作可能、 \(i=x+1\) が操作不可能であるとき、 \(x\) を操作すればよいです。

この \(x\) の周辺では \(A\) は次のようになっています。(操作可能な \(i\) と操作不可能な \(i\) が両方存在するため、 \(N\ge 3\) に限られます。)

\(A_x=a,A_{x+1}=-b,A_{x+2}=b \ (a \neq b)\) \(A=(\cdots, a, -b, b ,\cdots)\)

このとき、 \(i=x\) として操作すると次のようになります。

\(A=(\cdots, a-b, b ,\cdots)\)

ここで、 \(a-b+b \neq 0\) なので操作可能な \(i\) が存在しています。

\(i=x\) が操作可能、 \(i=x-1\) が操作不可能であるときも同様に \(i=x\) として操作してよいです。

操作不可能な \(i\) が存在しないとき

\(i=1\) として操作を行えばよいです。

\(N \ge 4\) の場合を考えます。 このとき、 \(A=(a,b,c,d\cdots) (a+b \neq 0,b+c \neq 0,c+d \neq 0)\) となっています。 \(i=1\) として操作を行うと、 \(A=(a+b,c,d,\cdots)\) となりますが、 \(c+d \neq 0\) なので操作可能な \(i\) が存在しています。

\(N=2\) の場合は自明であり、 \(N=3\) の場合も \(A\) の総和が \(0\) ではないという仮定と \(N=2\) の結果から操作可能です。

実装

操作不可能な \(i\) が連続しているとき、「操作不可能な \(i\) が存在するとき」の操作を繰り返すことで操作不可能な \(i\) が存在しないようにできます。 あとは「操作不可能な \(i\) が存在しないとき」の考察を用いて前から順に操作することができます。