数を小さくしてソルバーと総当たり解を照合。

In[3]:= nn=123;

In[4]:= n=4;

In[5]:= m=5;

In[6]:= solve[nn,n,m]

45777326
Out[6]= ---------
228886641

In[7]:=
In[7]:= #==0& /@ Mod[Total /@ Tuples[Range[nn],n],m] // Boole // Mean

45777326
Out[7]= ---------
228886641

よさげ。