题目描述

这里是欢乐的进香河，这里是欢乐的幼儿园。

今天是 2 月 14 日，星期二。在这个特殊的日子里，老师带着同学们欢乐地跳着，笑着。校长从幼儿园旁边的小吃店买了大量的零食决定分给同学们。听到这个消息，所有同学都安安静静地排好了队，大家都知道，校长不喜欢调皮的孩子。

同学们依次排成了一列，其中有 $A$ 位小朋友，有三个共同的欢乐系数 $O$，$S$ 和 $U$。如果有一位小朋友得到了 $x$ 个糖果，那么她的欢乐程度就是 $f(x)=Ox^2+Sx+U$。

现在校长开始分糖果了，一共有 $M$ 个糖果。有些小朋友可能得不到糖果，对于那些得不到糖果的小朋友来说，欢乐程度就是 $1$。如果一位小朋友得不到糖果，那么在她身后的小朋友们也都得不到糖果（即这一列得不到糖果的小朋友一定是最后的连续若干位）。

所有分糖果的方案都是等概率的。现在问题是：期望情况下，所有小朋友的欢乐程度的乘积是多少？呆呆同学很快就有了一个思路，只要知道总的方案个数 $T$ 和所有方案下欢乐程度乘积的总和 $S$，就可以得到答案 $ans=\frac{S}{T}$。现在他已经求出来了 $T$ 的答案，但是 $S$ 怎么求呢？他就不知道了。你能告诉他么？

因为答案很大，你只需要告诉他 $S$ 对 $P$ 取模后的结果。

后记：

虽然大家都知道，即便知道了 $T$，知道了 $S$ 对 $P$ 取模后的结果，也没有办法知道期望情况下，所有小朋友欢乐程度的乘积。但是，当呆呆想到这一点的时候，已经彻底绝望了。

输入格式

第一行有两个整数，分别是 $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$。

数据范围：

对于 $40 \%$ 的数据，$M \leq 150$。
对于 $60 \%$ 的数据，$M \leq 2000$。
对于 $80 \%$ 的数据，$M \leq 6000$。
对于 $100 \%$ 的数据，$M \leq 10000, P \leq 255, A \leq 10^8, O \leq 4, S \leq 300, U \leq 100$。