(より詳しい解説は後日ブログで公開します)

任意の整数 \(x\) に対して \(g(x)\) が \(3^{19}\) で割り切れるような整数係数多項式 \(g \ne 0\) を見つければ，入力の \(f\) を \(f \bmod g\) に置き換えてよくなり，\(O((M+N) \deg(g))\) 時間で解けます．

\(g\) としては \(g(x) = (x(x-1)(x-2))^{19}\) や \(g(x) = (x-0)(x-1) \cdots (x-41)\) が条件を満たします．