Let $f(x) = c_{d}x^{d}+c_{d-1}x^{d-1}+\dots +c_{1}x+c_{0}$. The residue condition on $a_{i}^{(n)}$ combined with the fact that $b-c\mid f(b)-f(c)$ for all integers $b,c$ implies: \[\gcd(m, g(m)) = \gcd(m, f(1)+f(2)+\dots +f(m))\]because we have $\sum\limits_{i=1}^{n} f(a_{i}^{(n)}) \equiv \sum\limits_{i=1}^{n} f(a_{i}^{(n)}\pmod n) \equiv \sum\limits_{i=1}^{n} f(i) \pmod n$. Note that we have: \[\sum\limits_{k=1}^{n} f(k) = \sum\limits_{k=1}^{n} \sum\limits_{j=0}^{d} c_{j}k^{j} = \sum\limits_{j=0}^{d} c_{j} \sum\limits_{k=1}^{n} k^{j}\]We'll prove the classical result $n\mid (j+1)!\sum\limits_{k=1}^{n} k^{j}$ for all $0\leq j\leq d$ by strong induction on $j$ with the base case $j=0$ being trivial. Assume that we've prove the induction hypothesis for $j=0, 1, \dots, m$. We'll prove the divisibility for $m+1$ as well. Denote \[S_{n, j} = 1^{j} + 2^{j} + \dots + n^{j}\]Then we write \[S_{n, m+2} = \sum\limits_{i=1}^{n} i^{m+2} \equiv \sum\limits_{i=2}^{n+1} i^{m+2} \equiv \sum\limits_{i=1}^{n} (i+1)^{m+2} = \sum\limits_{i=0}^{m+2} \binom{m+2}{i} S_{n, i}\pmod n\]\[\Longrightarrow (m+2)S_{n, m+1} +\binom{m+2}{2}S_{n, m}+\dots +\binom{m+2}{m+1}S_{n, 1}+\binom{m+2}{m+2}S_{n,0}\equiv 0\pmod n\]\[\Longrightarrow (m+2)!S_{n, m+1} +\binom{m+2}{2}(m+1)!S_{n, m}+\dots+(m+1)!S_{n,0}\equiv 0\pmod n\]\[\Longrightarrow (m+2)!S_{n,m+1}\equiv 0\pmod n\]Hence the induction step is complete. Finally, this implies that \[\frac{n}{(d+1)!}\mid \gcd(n, f(1)+f(2)+\dots +f(n)) = \gcd(n, g(n))\]therefore choosing $M = 2023^{2023}(d+1)!$ suffices.