随机数生成器 Beta Round ＃9 (酱油杯noi考后欢乐赛)

（每个测试点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改，原创。