JSOI2012 分零食

时间限制:10s      空间限制:256MB

题目描述

这里是欢乐的进香河,这里是欢乐的幼儿园。 
今天是2月14日,星期二。在这个特殊的日子里,老师带着同学们欢乐地跳着,笑着。校长从幼儿园旁边的小吃店买了大量的零食决定分给同学们。听到这个消息,所有同学都安安静静地排好了队,大家都知道,校长不喜欢调皮的孩子。 
同学们依次排成了一列,其中有A位小朋友,有三个共同的欢乐系数O,S和U。如果有一位小朋友得到了x个糖果,那么她的欢乐程度就是f(x)=O*x2+S*x+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取模后的结果。 


样例输入

4 100 
4 
1 
0 
0 

样例输出

63 

样例说明 
函数f(x)=x^2。一共有4份零食,4位同学。如果只有第一个同学得到,欢乐程度为16,若前两位同学得到,欢乐程度的所有可能依次为9,9,16,若有三位同学得到,欢乐程度有4,4,4,最后一种情况,每一个同学都得到了零食,欢乐程度为1。相加后得到S=63。 

应上传者要求,此题不公开,如有异议,请提出.

提示

对于100%的数据,M<=10000,P<=255,A<=108,O<=4,S<=300,U<=100。 


题目来源

没有写明来源