令 $M=\sum_{i=1}^NA_i$。我们对每个 $c\le M$ 计算恰好 $c$ 个集合的序列数量，通过容斥空集可以得到 $$ \sum_{x=0}^c(-1)^{c-x}{c\choose x}\prod_{i=1}^N{x\choose A_i} $$ 对所有 $c$ 求和就是答案。

令 $f(x)=\prod_{i=1}^N {x\choose A_i}$，因为 $A_i< P$，通过 Lucas 定理可知 $f(x+P)=f(x)$，所以我们按照 $x\bmod P$ 分类，可以得到答案等于 $$ \sum_{x=0}^{P-1}\sum_{c=x}^{P-1}\sum_{iP+x\le jP+c\le M}(-1)^{(j-i)P+(c-x)}{j\choose i}{c\choose x } f(x) $$ 因为固定 $x,y,j$ 的时候，$i$ 的贡献是 $\sum_{i=0}^j(-1)^{j-i}{j\choose i}=[j=0]$，所以上述求和可以化简为 $$ \sum_{x=0}^{P-1}f(x)\sum_{c=x}^{P-1}(-1)^{c-x}{c\choose x} $$ 而事实上在 $\bmod P$ 意义下，有 $$ \begin{aligned} &\sum_{c=x}^{P-1}(-1)^{c-x}{c\choose x}\\ =&\sum_{i=0}^{P-1-x}(-1)^i{x+i\choose i}\\ =&\sum_{i=0}^{P-1-x}{-1-x\choose i}\\ =&\sum_{i=0}^{P-1-x}{P-1-x\choose i}\\ =&2^{P-1-x} \end{aligned} $$ 所以剩下的难点在于计算所有的 $f(x)$。

因为将组合数展开成下降幂以后，$f(x)$ 可以写成 $\prod_i (x-i)^{c_i}$ 的形式，我们找到 $P$ 的一个原根 $g$，令 $\log_g(x)$ 为 $x$ 的离散对数，则只需要计算 $\log_g f(x)=\sum_{i}c_i \log_g(x-i)$，这显然是一个卷积，可以在 $O(P\log P)$ 时间内解决。