基本方針

maxT=1018<260\text{max}T = 10^{18} < 2^{60} であるため、考えられる N,MN, M の値はどちらも 00 以上 6060 未満となります。

よって、この範囲の N,MN, M を全探索することで AC することができます。

実装例(C++)