這題希望你的時間複雜度是$O(Q(\log Q)^2 + K\log K)$。經過實測，確定在ZJ上$O(QK)$的naïve演算法沒辦法在$30$秒內跑完。

不難發現令$f(x) = c_0 + c_1x + \ldots + c_Kx^K$，則題目問的就是$f(a_1), f(a_2), \ldots, f(a_Q)$除以$M$的餘數。
假定你知道怎麼把兩個$O(d)$次多項式間的乘法和除法做到時間複雜度$O(d\log d)$。
我們想算$f(a_i)$，一個方法是計算$f(x)$除以$x-a_i$的餘式，但不幸的是直接計算$f(x)$除以每個$x-a_i$的餘式還是$O(QK)$的。
以下我們介紹一個使用divide and conquer降低時間複雜度的做法。

在$[1, Q]$區間建立一棵線段樹，其中負責$[l, r]$區間的節點儲存多項式$p(x; l, r) := (x-a_l)(x-a_{l+1})\ldots(x-a_r)$。
可以發現，建好這棵線段樹的時間複雜度是$T(Q) = 2T(\frac{Q}{2})+O(Q\log Q) = O(Q(\log Q)^2)$。
接著，令$l<r$並設$m=\lfloor\frac{l+r}{2}\rfloor$。假定我們想要計算某個多項式$g(x)$除以$x-a_l, x-a_{l+1}, \ldots, x-a_r$的餘式們，我們可以先計算$g(x)$除以$p(x; l, r)$的餘式$h(x)$，再分別計算「$h(x)$除以$x-a_l, x-a_{l-1}, \ldots, x-a_m$的餘式們」和「$h(x)$除以$x-a_{m+1}, x-a_{m+2}, \ldots, x-a_r$的餘式們」以得到答案。
在根節點的取餘運算要花$O(K\log K)$時間。另一方面，對於一個負責區間長度為$L$的節點，它傳下去的多項式次數必定不超過$L-1$，故剩下的節點的取餘運算時間總和為$2T(\frac{Q}{2}) = 4T(\frac{Q}{4}) + O(Q\log Q) = O(Q(\log Q)^2)$。
這樣一來，整體的時間複雜度就從$O(QK)$降低至$O(Q(\log Q)^2 + K\log K)$了。

關於多項式的運算，有個地方要注意一下。
這題的$M$可以到$10^8$，也就是$QM^2$可能破unsigned long long的範圍。
在寫乘法的時候，該對$M$取餘數的地方就不要偷懶。