题目描述

农夫约翰有 3×N（1 ≤ N ≤ 500000）头牛，编号依次为 0 … 3N−1。每头牛都有一个整数体重和一个“价值度” Ui。
比赛允许带 N 头牛参赛，目标是使选中牛的价值度总和最大；若能达到最大价值度的方案不止一个，则在这些方案中选择总体重最小的一组。请输出这组牛的总体重 对 M 取模 的结果（即总体重 mod M）。

为加速输入，体重和价值度由如下多项式生成（对每头牛 i）：

• 体重：Wi = (a×i^5 + b×i^2 + c) mod d
• 价值：Ui = (e×i^5 + f×i^3 + g) mod h

其中 0 ≤ a,b,c,d,e,f,g,h ≤ 10^9，i ∈ [0, 3N−1]。

输入格式

一行，包含 10 个用空格分隔的整数：
N, a, b, c, d, e, f, g, h, M

输出格式

一行，一个整数：价值度最高且在此基础上总体重最小的 N 头奶牛的总体重之和 mod M 的结果。

输入样例 #1

2 0 1 5 55555555 0 1 0 55555555 55555555

输出样例 #1

51

题目说明

示例生成的 6 头牛（i=0…5）的体重依次为 5、6、9、14、21、30；价值度依次为 0、1、8、27、64、125。
价值度最高的两头是 i=4 与 i=5（64 与 125），其体重之和为 21 + 30 = 51；