그랜드 팜오프

농부 존은 소 $3N$마리 ($1 \le N \le 500{,}000$)를 기르고 있으며, 각 소에는 $0$번부터 $3N-1$번까지 번호가 붙어 있습니다. 소 $i$는 정수 무게 $W_i$와 정수 유용도(utility) $U_i$를 가지며, 두 값 모두 아래 공식으로 생성됩니다.

농부 존은 자신의 소들을 지역 농업 공동체에 선보이는 농장 경연 대회 "그랜드 팜오프"에 참가합니다. 이 대회에는 정확히 소 $N$마리를 데려갈 수 있으며, 존은 데려가는 $N$마리의 유용도 합이 최대가 되도록 하고 싶어 합니다.

유용도 합을 최대로 만드는 $N$마리 조합은 여러 가지일 수 있습니다. 대회가 참가 소들의 총 무게에 제한을 둘 수도 있으므로, 존은 부차적인 기준으로 총 무게가 더 가벼운 조합을 선호합니다.

유용도 합이 최대인 $N$마리 조합들 가운데 총 무게가 최소인 것을 찾아, 그 최소 총 무게를 $M$ ($10{,}000{,}000 \le M \le 1{,}000{,}000{,}000$)으로 나눈 나머지를 출력하세요.

각 소 $i$ ($0 \le i < 3N$)의 값은 다음과 같이 계산됩니다.

$W_i = (a \cdot i^5 + b \cdot i^2 + c) \bmod d$

$U_i = (e \cdot i^5 + f \cdot i^3 + g) \bmod h$

계수의 범위는 다음과 같습니다.

• $0 \le a, b, c, e, f, g \le 1{,}000{,}000{,}000$
• $10{,}000{,}000 \le d, h \le 1{,}000{,}000{,}000$

이 공식은 때때로 같은 값을 여러 번 만들어 낼 수 있으므로, 알고리즘은 중복을 올바르게 처리해야 합니다.

• 첫째 줄: 공백으로 구분된 정수 10개 — $N$, $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$, $M$

• 유용도 합을 최대로 하는 $N$마리 선택 모두 가운데 총 무게의 최솟값을 $M$으로 나눈 나머지를 한 줄에 출력합니다.

이 공식은 무게 $5, 6, 9, 14, 21, 30$과 유용도 $0, 1, 8, 27, 64, 125$를 생성합니다. 유용도가 가장 높은 두 소는 $i=4$번과 $i=5$번이며, 이들의 무게 합은 $21 + 30 = 51$입니다.