Problem Description

This is the joyful Jingxiang River, and this is a joyful kindergarten.

Today is February 14, Tuesday. On this special day, the teacher leads the children to dance and laugh happily. The principal bought a large amount of snacks from a snack shop next to the kindergarten and decided to give them to the children. Hearing this news, all the children quietly lined up. Everyone knows that the principal does not like naughty kids.

The children stand in a single line in order. There are $A$ children, and there are three shared joy coefficients $O$, $S$, and $U$. If a child receives $x$ candies, then her happiness is $f(x)=Ox^2+Sx+U$.

Now the principal starts handing out candies. There are $M$ candies in total. Some children may receive no candies. For those children who receive no candies, the happiness is $1$. If a child receives no candies, then all children behind her also receive no candies (that is, the children who receive no candies must form a consecutive suffix at the end of the line).

All candy-distribution plans are equally likely. The question is: in expectation, what is the product of the happiness values of all children? Student Daidai quickly came up with an idea: as long as he knows the total number of plans $T$ and the sum $S$ of the happiness-product over all plans, he can get the answer $ans=\frac{S}{T}$. He has already computed $T$, but he does not know how to compute $S$. Can you tell him?

Because the answer is very large, you only need to output $S \bmod P$.

Postscript:

Although everyone knows that even if you know $T$ and $S \bmod P$, there is still no way to know the expected product of the happiness values of all children. However, when Daidai realized this, he was already completely hopeless.

Input Format

The first line contains two integers, $M$ and $P$.

The second line contains an integer $A$.

The third line contains an integer $O$.

The fourth line contains an integer $S$.

The fifth line contains an integer $U$.

Output Format

Output one integer $S$. Since the answer may be very large, you only need to output $S \bmod P$.

4 100
4
1
0
0

63

Hint

Sample Explanation:

The function is $f(x)=x^2$. There are $4$ snacks and $4$ students. If only the first student receives candies, the happiness is $16$. If the first two students receive candies, then the possible happiness values (for all distributions) are $9, 9, 16$ in order. If three students receive candies, the happiness values are $4, 4, 4$. In the last case, every student receives snacks, and the happiness is $1$. Adding them up gives $S=63$.

Constraints:

For $40\%$ of the testdata, $M \leq 150$.
For $60\%$ of the testdata, $M \leq 2000$.
For $80\%$ of the testdata, $M \leq 6000$.
For $100\%$ of the testdata, $M \leq 10000, P \leq 255, A \leq 10^8, O \leq 4, S \leq 300, U \leq 100$.

Translated by ChatGPT 5