(每个测试点2s)

背景

做了noi2012的随机数生成器之后,PLQ觉得这题太水了,于是他又想出了一个问题,然而他把自己虐了,实在做不出来,只能向你求教。

描述

已知X0,除X0之外Xi=(P((aXi-1+k)mod m))mod m,P为一个函数,作用是将数字反转,如P(123)=321;P(100)=1。给出a、k、m、X0、n,求Xn的值。

输入格式

输入只有一行,这一行有五个用空格隔开的整数a、k、m、X0、n。

输出格式

输出只有一个数字,为Xn

样例输入1

5 7 11 2 4

样例输出1

1

样例输入2

999998 577222 10007 12 1800000000

样例输出2

1173

数据范围与约定

  • 100%的数据,0<n≤10000000000000000,0<m≤2000000000,0<a,k≤10000000,0≤X0<m。

来源

noi2012 day1 T1改,原创。