描述
这里是欢乐的进香河，这里是欢乐的幼儿园。
今天是2月14日，星期二。在这个特殊的日子里，老师带着同学们欢乐地跳着，笑着。校长从幼儿园旁边的小吃店买了大量的零食决定分给同学们。听到这个消息，所有同学都安安静静地排好了队，大家都知道，校长不喜欢调皮的孩子。
同学们依次排成了一列，其中有A位小朋友，有三个共同的欢乐系数O，S和U。如果有一位小朋友得到了x个糖果，那么她的欢乐程度就是f(x)=Ox^2+Sx+U。
现在校长开始分糖果了，一共有M个糖果。有些小朋友可能得不到糖果，对于那些得不到糖果的小朋友来说，欢乐程度就是1。如果一位小朋友得不到糖果，那么在她身后的小朋友们也都得不到糖果。（即这一列得不到糖果的小朋友一定是最后的连续若干位）
所有分糖果的方案都是等概率的。现在问题是：期望情况下，所有小朋友的欢乐程度的乘积是多少？呆呆同学很快就有了一个思路，只要知道总的方案个数T和所有方案下欢乐程度乘积的总和S，就可以得到答案Ans=S/T。现在他已经求出来了T的答案，但是S怎么求呢？他就不知道了。你能告诉他么？
因为答案很大，你只需要告诉他S对P取模后的结果。
后记：
虽然大家都知道，即便知道了T，知道了S对P取模后的结果，也没有办法知道期望情况下，所有小朋友欢乐程度的乘积。但是，当呆呆想到这一点的时候，已经彻底绝望了。
格式
输入格式
第一行有2个整数，分别是M和P。
第二行有一个整数A，第三行有一个整数O。
第四行有一个整数S，第五行有一个整数U。
输出格式
一个整数S，因为答案可能很大，你只需要输出S 对P取模后的结果。
看到很多大佬虐这道题，我也很好奇就写了写。
题里直接给了个生成函数$c$和一个卷积的形式$c^x$,如果题里没有要求拿到糖的人是一个前缀的话直接令$c[0]=1$求一发多项式快速幂就行了。
但有了限制之后，考虑枚举得到糖的人数，因为不能有人没有糖，令$c[0]=0$。
设$f[i]$表示只有i个糖时的答案，最后答案为$f[m]$,则
$$f=\sum_{i=1}^{A}c^i$$
感觉如果模数合适的话应该可以等比数列求和直接做吧。。。开始还以为是一道水题
但显然这道题不行，那就考虑倍增。
设$g[i]=c^{2^i},sumg[i]=\sum_{i=1}^{2^i}c^i$
把$A$二进制拆分后用上边两个数组显然是可以求出来的，懒得写了。。。
注意FFT完往回赋值时只赋$0-m$,不要把FFT完的整个数组都赋回去，调了一晚上不知道哪错了。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define pi acos(-1)
#define N 50005
#define double long double
using namespace std;
struct E
{
double x,y;
E(){;}
E(double _x,double _y)
{
x=_x;y=_y;
}
friend E operator + (E a,E b)
{
return E(a.x+b.x,a.y+b.y);
}
friend E operator - (E a,E b)
{
return E(a.x-b.x,a.y-b.y);
}
friend E operator / (E a,double b)
{
return E(a.x/b,a.y/b);
}
friend E operator * (E a,E b)
{
return E(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
}a[N],b[N];
int R[N],n;
void fft(E *a,int f)
{
for(int i=;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);
for(int i=;i<n;i<<=)
{
E wn(cos(pi/i),f*sin(pi/i));
for(int j=;j<n;j+=(i<<))
{
E w(,);
for(int k=;k<i;k++,w=w*wn)
{
E x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y;a[j+k+i]=x-y;
}
}
}
if(f==-)
{
for(int i=;i<n;i++)a[i]=a[i]/(double)n;
}
return ;
}
int m,p,A,O,S,U;
int c[N];
int g[][N],sg[][N];
void make(int *a1,int *a2,int *a3)
{
for(int i=;i<n;i++)a[i].x=a[i].y=b[i].x=b[i].y=;
for(int i=;i<n;i++)a[i].x+=a2[i];
for(int i=;i<n;i++)b[i].x+=a3[i];
fft(a,);fft(b,);
for(int i=;i<n;i++)a[i]=a[i]*b[i];
fft(a,-);
for(int i=;i<=m;i++)a1[i]=(int)(a[i].x+0.2);
for(int i=;i<=m;i++)a1[i]%=p;
}
int gg[N];
void solve()
{
for(int i=;i<n;i++)g[][i]=c[i];
for(int i=;i<=;i++)make(g[i],g[i-],g[i-]);
for(int i=;i<n;i++)sg[][i]=c[i];
for(int i=;i<=;i++)
{
for(int j=;j<n;j++)sg[i][j]=sg[i-][j];
make(gg,sg[i-],g[i-]);
for(int j=;j<n;j++)
{
sg[i][j]=sg[i][j]+gg[j];
if(sg[i][j]>=p)sg[i][j]-=p;
}
}
return ;
}
int ans[N],now[N];
void pw(int y)
{
now[]=;
for(int i=;i>=;i--)
{
if(y&(<<i))
{
make(gg,now,sg[i]);
make(now,now,g[i]);
for(int j=;j<n;j++)
{
ans[j]=ans[j]+gg[j];
if(ans[j]>=p)ans[j]-=p;
}
}
}
return ;
}
int main()
{
scanf("%d%d%d%d%d%d",&m,&p,&A,&O,&S,&U);
S%=p;O%=p;U%=p;
for(int i=;i<=m;i++)c[i]=(1LL*O*i*i%p+1LL*S*i%p+U)%p;
n=;int l=;
while(n<=*m)n<<=,l++;
for(int i=;i<n;i++)R[i]=(R[i>>]>>)|((i&)<<(l-));
if(A>m)A=m;
solve();
pw(A);
printf("%d\n",ans[m]);
return ;
}