[SXZOI 2024 A] 急

题目背景

我们为什么要说“急了”？

急了是一种态度，一种张弛有度，一种睚眦必报，一种快意恩仇。遇到羞辱不急于还击，是懦夫，“急了”教我们让他绝不退让、以武服人；遇到挫折羞愤不已，是愚夫，“急了”教我们正面应敌、以武取胜。

“急了”体现的是中华法家的杀伐之道，体现的是忍子当头一把刀、我就是急了的人生哲理，所谓“心静即声沸，其间有古今”，学会“急了”，方能成长，方能成熟，方能于世间百态中以杀证道、纵横古今。

题目描述

给定函数 $f(x) = ax^2+bx+c$。

定义 $f^k(x) = f(f^{k-1}(x))$，边界为 $f^0(x)=x$。

现在给定 $n, x, p$，你需要求出 $f^n(x) \bmod p$ 的值。

输入格式

第一行三个非负整数 $a, b, c$。

第二行三个非负整数 $n, x, p$。

输出格式

一行一个非负整数，表示答案。

样例 #1

样例输入 #1

2 4 4
8 3 5

样例输出 #1

2

样例 #2

样例输入 #2

114 514 1919
998244353 810 100007

样例输出 #2

54567

提示

数据范围

对于所有数据，保证 $0 \leq a, b, c, x < p \leq 2 \times 10^7, 0 \leq n \leq 10^{18}$。

对于 $20%$ 的数据，保证 $0 \leq n \leq 10^6$。

对于另外 $40%$ 的数据，保证 $0 \leq p \leq 10^6$。