隐藏的余数转盘

题目描述

数列定义为 x_0 已知，x_(k+1)=(p×x_k+q) mod m。给定 n，求 x_n。

输入格式

一行输入 x_0、p、q、m、n，满足 0≤x_0,p,q≤10^9、1≤m≤2×10^5、0≤n≤10^18。

输出格式

输出 x_n。n=0时输出 x_0 mod m。

样例

输入

1 2 1 5 2026

输出

2