要求的就是 ${n\brack k}_q\bmod p$。

它等于 $\frac{[n]_q!}{[k]_q![n-k]_q!}$，其中 $[n]_q!=[1]_q[2]_q\cdots[n]_q,[n]_q=\frac{1-q^n}{1-q}$。

如果 $q=0$，那么答案显然是 $1$。

令 $r$ 为最小的正整数满足 $q^r\equiv 1\pmod p$。那么问题在于 $[kr]_q$ 在 $\bmod p$ 意义下等于 $0$。注意到 $[kr]_q=[k]_{q^r}[r]_q=k[r]_q$，所以 $[n]!=\lfloor n/r\rfloor!([r]_q!)^{\lfloor n/r \rfloor}[n\bmod r]_q!$。只需要用 $x\cdot p^a\cdot [r]_q^b$ 的形式记录答案即可。