题目描述

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

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

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

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

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

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

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

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

输入格式

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

输出格式

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

样例

输入样例

2 0 1 5 55555555 0 1 0 55555555 55555555

输出样例

51

提示

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