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

不難發現令$f(x)=c_0+c_{1}x+\dots +c_K{x}^K$，則題目問的就是$f(a_1),f(a_2),\dots ,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})\dots (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},\dots ,x-a_r$的餘式們，我們可以先計算$g(x)$除以$p(x;l,r)$的餘式$h(x)$，再分別計算「$h(x)$除以$x-a_l,x-a_{l-1},\dots ,x-a_m$的餘式們」和「$h(x)$除以$x-a_{m+1},x-a_{m+2},\dots ,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$，也就是$Q{M}^2$可能破unsigned long long的範圍。
在寫乘法的時候，該對$M$取餘數的地方就不要偷懶。