Farmer John owns 3N (1 <= N <= 500,000) cows surprisingly numbered 0..3N-1, each of which has some associated integer weight W_i (1 <= W_i <= d). He is entering the Grand Farm-off, a farming competition where he shows off his cows to the greater agricultural community.</p>

This competition allows him to enter a group of N cows. He has given each of his cows a utility rating U_i (1 <= U_i <= h), which represents the usefulness he thinks that a particular cow will have in the competition, and he wants his selection of cows to have the maximal sum of utility.

There might be multiple sets of N cows that attain the maximum utility sum. FJ is afraid the competition may impose a total weight limit on the cows in the competition, so a secondary priority is to bring lighter weight competition cows.

Help FJ find a set of N cows with minimum possible total weight among the sets of N cows that maximize the utility, and print the remainder when this total weight is divided by M (10,000,000 <= M <= 1,000,000,000).

Note: to make the input phase faster, FJ has derived polynomials which will generate the weights and utility values for each cow. For each cow 0 <= i < 3*N,

       W_i = (ai^5+bi^2+c) mod d
 and   U_i = (ei^5+fi^3+g) mod h

with reasonable ranges for the coefficients (0 <= a <= 1,000,000,000; 0 <= b <= 1,000,000,000; 0 <= c <= 1,000,000,000; 0 <= e <= 1,000,000,000; 0 <= f <= 1,000,000,000; 0 <= g <= 1,000,000,000; 10,000,000 <= d <= 1,000,000,000; 10,000,000 <= h <= 1,000,000,000).

The formulae do sometimes generate duplicate numbers; your algorithm should handle this properly.

입력 형식

• Line 1: Ten space-separated integers: N, a, b, c, d, e, f, g, h, and M

출력 형식

• Line 1: A single integer representing the lowest sum of the weights of the N cows with the highest net utility.
</ul>

 

예제 입력

2 0 1 5 55555555 0 1 0 55555555 55555555

예제 출력

51

힌트

The functions generate weights of 5, 6, 9, 14, 21, and 30 along with utilities of 0, 1, 8, 27, 64, and 125.</p>

The two cows with the highest utility are cow 5 and 6, and their combined weight is 21+30=51.