Nông dân John có \(3 \times N\) con bò \((1 \le N \le 500,000)\), được đánh số từ \(0\) đến \(3 \times N-1\). Mỗi con bò có một trọng lượng nguyên \(W_i\) \((1 \le W_i \le d)\).

John chuẩn bị tham gia một cuộc thi nông trại lớn – nơi ông sẽ mang một nhóm bò đến trình diễn trước cộng đồng nông nghiệp. Theo luật, ông chỉ được mang đúng \(N\) con bò đến tham gia.

Mỗi con bò còn được John gán một chỉ số "mức độ hữu ích" \(U_i (1 \le U_i \le h)\), thể hiện mức độ hữu ích của nó trong cuộc thi. Mục tiêu của John là chọn ra \(N\) con bò có tổng độ hữu ích lớn nhất.

Tuy nhiên, nếu có nhiều cách chọn \(N\) con bò đạt tổng hữu ích tối đa, thì ông muốn chọn tổ hợp có tổng trọng lượng thấp nhất trong số đó.

Nhiệm vụ của bạn là giúp John chọn \(N\) con bò sao cho:

Tổng độ hữu ích là tối đa.

Trong số những tổ hợp thỏa điều kiện trên, tổng trọng lượng là nhỏ nhất.

Sau đó in ra phần dư của tổng trọng lượng đó chia cho \(M\) (với \(10^7 \le M \le 10^9\)).

Tạo dữ liệu đầu vào Để tăng tốc nhập liệu, trọng lượng và độ hữu ích của từng con bò được tạo tự động từ các đa thức:

Với mỗi con bò \(i\) \((0 \le i < 3×N)\):

\[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\]

\[(0\le a,b,c,d,e,f,g,h\le 10^9)\]

Các hàm có thể sinh ra giá trị trùng lặp - bạn cần xử lý đúng.

Dữ liệu vào

• Một dòng duy nhất gồm 10 số nguyên cách nhau bởi dấu cách: "N a b c d e f g h M"

Dữ liệu ra

• Một dòng duy nhất: phần dư khi tổng trọng lượng nhỏ nhất (trong số các nhóm \(N\) con bò có tổng độ hữu ích lớn nhất) chia cho \(M\).

Input 1

2 0 1 5 55555555 0 1 0 55555555 55555555

Output 1

51

Giải thích

Công thức sinh ra trọng lượng và độ hữu ích như sau (với \(i\) từ \(0\) đến \(5\)):