ll@N,@P,@C,a=(C<1)*N*(N+1)/2,l;vector<vector<ll>>A(1,{1});rep(N){ll@n;if(n)A.back().push_back(n);else A.push_back({1});}REP[A](v,A.size()){l=v.size();if(C){rep(i,1,l){(v[i]*=v[i-1])%=P;REP(j,0,i)a+=C*v[j]%P==v[i];}}else a-=l*(l-1)/2;}wt(a);