题目描述

农夫约翰有$\red{3N(1≤}$$\red{N≤}$$\red{500000)}$头牛，编号依次为$\red{1...3N，}$每头牛都有一个整数值的体 重$\red{W_i(1≤}$$\red{W_i≤}$$\red{d)，}$约翰准备参加农场技艺大赛，向广大的农业社区展示他的奶牛

大赛规则允许约翰带$\red{N}$头牛参赛.约翰给每头牛赋予了一个"有用度"$\red{U_i(1≤}$$\red{U_i≤}$$\red{h),}$它表 示了某头牛在比赛中的有用程度，约翰希望他选出的奶牛的有用度之和最大.

有可能选出很多组的$\red{N}$头牛都能达到有用度最大和.约翰害怕选出的$\red{N}$头牛的总重量会给大赛 带来震撼，所以，要考虑优先选择体重轻的奶牛.

帮助约翰选出$\red{N}$头总重量最轻，并且有用度之和最大的奶牛，输出体重模$\red{M(10^7≤}$$\red{M≤}$ $\red{10^9)}$后的余数.

注意:为了使输入更快，约翰使用了一个多项式来生成每头牛的体重和有用度.对每头牛$\red{I,}$ 体重和有用度的计算公式为:

$\red{W_I=(aI^5+bI^2+c) mod d}$

$\red{U_I=(eI^5+fI^3+g) mod h}$

各个 系数的取值范围为: $\red{0≤}$$\red{a,b,c,e,f,g≤}$$\red{10^9，}$$\red{10^7≤}$$\red{d,h≤}$$\red{10^9.}$这个多项式有时会生成重 复的数，你的程序要正确处理这种情况.

输入格式

第$\red{1}$行：$\red{10}$个空格分开的整数: $\red{N, a, b, c, d, e, f, g, h, M}$

输出格式

第$\red{1}$行：满足总重量最轻，且用度之和最大的$\red{N}$头奶牛的总体重模$\red{M}$后的余数。

样例

输入样例

2 0 1 5 55555555 0 1 0 55555555 55555555

输出样例

51

提示

样例说明：公式生成的体重和有用度分别为： 体重：$\red{5, 6, 9, 14, 21, 30 }$有用度：$\red{0, 1, 8, 27, 64, 125.}$