jiangly 太神啦~。

自己只能想出一个单位根反演的垃圾做法，根本没直接往循环卷积考虑……

$$ans=\sum_i[i\equiv r\pmod k][z^i](1+z)^{nk}\\=[z^r]((1+z)^{nk}\bmod(z^k-1)) $$

直接做就好了。

$k\ge10^5$ 也是理论可做的。但真的有谁会去闲的没事写 Bluestein/倍增 FFT 吗？更何况模数与 $k$ 之间关系不定，单位根不存在，只能模分圆多项式这怎么 CZT 啊。

一个坑点是 $k=1$ 是容许的……

typedef AnyMod::ModInt modint;
uint k;
struct poly
{
    modint A[50];
    modint&operator[](uint n){return A[n];}
    friend poly operator*(poly a,poly b)
    {
        poly ans;
        for(uint i=0;i<k;i++)for(uint j=0;j<k;j++)ans[(i+j)%k]+=a[i]*b[j];
        return ans;
    }
    friend poly operator^(poly a,ullt b)
    {
        poly ans;ans[0]=1;
        while(b)
        {
            if(b&1)ans=ans*a;
            a=a*a,b>>=1;
        }
        return ans;
    }
};
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    // freopen("QAQ.out","w",stdout);
#endif
    uint n,r,p;scanf("%u%u%u%u",&n,&p,&k,&r);AnyMod::ChgMod(p);
    poly P;P[0]=1,P[1%k]+=1;P=P^k^n;
    P[r].println();
    return 0;
}