P0903

[Usaco2009 Nov]农场技艺大赛

[Usaco2009 Nov]农场技艺大赛

有 3N3N 头奶牛，编号为 0,1,…,3N−10,1,\ldots,3N-1。编号为 ii 的奶牛体重为

Wi=(a×i5+b×i2+c) mod d，W_i=(a\times i^5+b\times i^2+c)\bmod d，

有用度为

Ui=(e×i5+f×i3+g) mod h。U_i=(e\times i^5+f\times i^3+g)\bmod h。

你需要恰好选择 NN 头奶牛。首先，要求所选奶牛的有用度总和最大；如果有多种方案的有用度总和相同且均为最大值，则选择总体重最小的方案。

输入格式

输入一行 1010 个以空格分隔的整数 N,a,b,c,d,e,f,g,h,MN,a,b,c,d,e,f,g,h,M。

输出格式

输出一个整数，表示最优方案的总体重对 MM 取模后的余数。

样例输入

2 0 1 5 55555555 0 1 0 55555555 55555555

样例输出

51

样例解释

样例中，公式生成的体重依次为 55、66、99、1414、2121、3030，有用度依次为 00、11、88、2727、6464、125125。

选择编号为 44、55 的奶牛时，有用度总和最大，其总体重为 21+30=5121+30=51。

数据范围

  • 1≤N≤2500001\le N\le 250000；
  • 0≤a,b,c,e,f,g≤1090\le a,b,c,e,f,g\le 10^9；
  • 1≤d,h,M≤1091\le d,h,M\le 10^9。

来源与许可

本题为 USACO 2009 November 试题「农场技艺大赛」，题面与测试数据整理自 BZOJ。

样例 1

输入

2 0 1 5 55555555 0 1 0 55555555 55555555

输出

51