description
给定一个质数 \(m\)，以及 \(n,x\) 和集合 \(S\)。从集合 \(S\) 中任意选数构成长度为 \(n\) 的数列（一个数可以选多次），求数列元素乘积模 \(m\) 等于 \(x\) 的数列的数量。模 \(1004535809\)。
\(3\leq m\leq 8000\)
\(1\leq n\leq 10^9\)
\(|S|\leq m,0\leq x<m\)
solution
发现 \(m\) 是奇素数，所以存在模 \(m\) 的原根 \(g\)，且 \([1,m-1]\) 中的每个整数都可以用 \(g\) 的 \([0,m-2]\) 次幂表示。设 \(a\) 的指标 \(I(a)\) 满足 \(g^{I(a)}=a\)。则根据离散对数的运算法则，要求数列中的数的指标的和模 \(\varphi(m)\) 等于 \(I(x)\)。可以 BSGS 求出 \(x\) 和 \(S\) 中数的指标。
于是问题变成从集合中选 \(n\) 个数，使它们的和在模意义下等于一个数。
由于 \(1004535809\) 是个 NTT 模数，直接构造多项式，进行快速幂即可。每次卷积后把大于等于 \(\varphi(m)\) 的次数的项的次数模 \(\varphi(m)\) 存起来即可。
时间复杂度 \(O(|S|\sqrt{m}+m\log m\log n)\)
hint
求 \(m\) 的原根可以直接从小到大枚举，根据原根定理判定即可。