Farm Competition Cow Selection

Farmer John owns \(3N\) cows numbered from 0 to \(3N-1\). Each cow \(i\) has an associated weight \(W_i\) and utility rating \(U_i\) generated by the following polynomial formulas:

\(W_i = (a \times i^5 + b \times i^2 + c) \mod d\)

\(U_i = (e \times i^5 + f \times i^3 + g) \mod h\)

The competition rules allow Farmer John to select exactly \(N\) cows. His primary objective is to maximize the sum of the utility ratings of the chosen cows. If there are multiple ways to achieve the maximum total utility, he picks the set with the minimum total weight. Your task is to compute the sum of the weights of the selected cows modulo \(M\).

Note: The parameters \(a, b, c, d, e, f, g, h, M\) along with \(N\) are provided in the input, and the values for individual cows are generated via the above formulas.

inputFormat

The input consists of a single line containing 10 space‐separated integers:

N a b c d e f g h M

Here:

• \(N\) is the number of cows to select (with \(1 \le N \le 500000\)).
• The total number of cows is \(3N\), indexed from 0 to \(3N-1\).
• \(W_i = (a \times i^5 + b \times i^2 + c) \mod d\) is the weight of cow \(i\) (with \(1 \le W_i \le d\)).
• \(U_i = (e \times i^5 + f \times i^3 + g) \mod h\) is the utility rating of cow \(i\) (with \(1 \le U_i \le h\)).
• \(M\) is the modulus for the final answer (\(10,000,000 \le M \le 1,000,000,000\)).

outputFormat

Output a single integer, which is the sum of the weights of the \(N\) selected cows (i.e. those that yield the maximum total utility and, among these, have the minimum total weight) taken modulo \(M\).

sample

1 1 1 1 10 1 1 1 10 10000000

3