第k顺序统计量

题目描述

给定3个整数A, B, C, 和数组第一个数a[1]。数组a由如下方式得到。询问a中第k小的数是多少。

for(int i = 2; i <= 3000000; ++i)
    a[i] = ((1LL * a[i - 1] * A ^ B) + C) % 1000000007;

输入

多组组数据，每组数据一行，数据组数不超过7

每行5个整数A, B, C, a[1], k (保证五个数为int范围内正整数且k在3000000范围内)

输出

对于每组数据，输出一行，第k小的数。

输入样例

4 5 6 7 8

输出样例

972