Candy Distribution Happiness Product

In a joyful kindergarten on February 14th, a principal has decided to distribute a total of M candies among A children standing in a line. The children are arranged such that if one child does not receive any candy, then every child behind that child will also receive none.

For each child who receives x candies (x ≥ 1), the happiness is defined by the function \(f(x)= O x^2 + S x + U\). If a child receives no candy, the happiness is defined to be 1.

A valid distribution is determined by choosing an integer k (with \(0 \le k \le A\)) such that:

• If \(k > 0\), the first k children receive candies (each at least one candy) and their total sum is M, while the remaining \(A-k\) children automatically receive 0 candies.
• If \(k = 0\) then no child receives any candy (this case is only possible when \(M=0\)).

For each valid distribution, compute the product of the happiness values of all A children. Let \(S\) be the sum of these products over all valid distributions. Given a modulus \(P\), your task is to compute \(S \bmod P\).

Note: The total number of distributions (denoted by \(T\)) is not needed for your calculation. You simply need to compute \(S\) mod \(P\), where for a distribution with a selected k (\(1 \le k \le \min(A, M)\)) the contribution is

\[ \sum_{x_1+\cdots+x_k=M, \; x_i\ge 1}\;\prod_{i=1}^{k} \Bigl(O x_i^2 + S x_i + U\Bigr)\,, \]

and if \(M=0\), there is exactly one valid distribution with all children getting 0 candies (happiness 1 each).

inputFormat

The input consists of a single line with six space-separated integers:

• \(A\): the number of children,
• \(M\): the total number of candies,
• \(O, S, U\): the parameters in the happiness function \(f(x)= O x^2 + S x + U\),
• \(P\): the modulus.

outputFormat

Output a single integer representing \(S \bmod P\), where \(S\) is the sum of the happiness product over all valid candy distributions.

sample

3 5 1 1 1 1000

131