#2221. 「HEOI2014」南园满地堆轻絮

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 Z 是 ZRP(Zombies’ Republic of Poetry,僵尸诗歌共和国)的一名诗歌爱好者,最近他研究起了诗词音律的问题。在过去,诗词是需要编成曲子唱出来的,比如下面这首《菩萨蛮》,唱出来的话其对应 的音符就是这样的:

南 园 满 地 堆 轻 絮, 愁 闻 一 霎 清 明 雨
   1 1 5 5 6 6 5  4 4 3 3 2 2 1

因而可以发现,“1 1 5 5 6 6 5 4 4 3 3 2 2 1” 这串音符就成为了研究音律的关键。

小 Z 翻阅了众多史料发现,过去的一首曲子的音调是不下降的。小 Z 想要知道对于一首给定的曲子,如何通过提高音调或者降低音调,将它的音调修改得不下降, 而且使得修改幅度最大的那个音符的修改幅度尽量小。

即如果把一个包含 n 个音符的曲子看做是一个正整数数列 A_1,\ldots,A_n ,那么目标是求另一个正整数数列 B_1,\ldots,B_n , 使得对于任意的 1 \leq i < n B_i \leq B_{i+1} ,而且使得 \mathrm{Ans}= \max_{1 \leq j \leq n} \{|A_j-B_j|\} 尽量小。  小 Z 很快就想清楚了做法,但是鉴于他还忙着写诗, 所以这个任务就交给了你。

输入格式

由于数据规模可能较大,因此采用如下方式生成数据。

每个数据包含六个数: n,S_a,S_b,S_c,S_d,A_1,\mathrm{Mod} ,意为共有 n 个音符,第一个音符为 A_1
生成规则如下: 定义生成函数 F(x) = S_ax^3 + S_bx^2 + S_cx + S_d
那么给出递推公式 A_i = F(A_{i-1}) + F(A_{i-2}) ,此处规定 A_0 = 0 。   由于中间过程的数可能会特别大,所以要求每一步与 A 中的每个数都对一个给定的数 \mathrm{Mod} 取模。

输出格式

输出一行,包含一个正整数 \mathrm{Ans}

样例

样例输入

3 815 6901 3839 178 199 10007

样例输出

1334

样例解释

生成的数列为 199~4568~1901 ,此时将 4568 修改为 3234 1901 也修改为 3234 即可,代价为 1334

数据范围与提示

对于 100\% 的数据, n \leq 5000000,\ S_a,S_b,S_c,S_d,A_1 \leq 10000,\ \mathrm{Mod} \leq 1000000007