该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

老师奖励给你一个带密码的本子，密码是 $0\sim 9999$ 的一个整数。这个密码本很有意思，假设当前密码为 $x$，用这个密码把锁开一次之后，密码就会变成 $x^2+C$ 除以 $10000$ 的余数， $C$ 是固定值。

现在有初始密码 $x_1$ 和设置的 $C$，以及这是第 $k$ 次开锁，请帮忙计算$k$ 次后密码是多少。

输入格式

输入一行三个正整数 $x_1,C,k$，表示初始密码、设置的 $C$，以及这是第几次开锁。

输出格式

输出一行一个自然数，表示这一次开锁的密码。

1000 3 1

1000

1000 3 2

3

1000 3 3

12

提示

【样例解释】

三个样例的初始密码都是 $1000$，$C$ 均为 $3$。

第一次开门时的密码就是初始密码 $1000$。

第一次开门后，密码会变成 $1000^2+3$ 对 $10000$ 取余的结果，也就是 $3$，因此第二次开门的密码为 $3$。

第二次开门后，密码会变成 $3^2+3$ 对 $10000$ 取余的结果，也就是 $12$，因此第三次开门的密码为 $12$。

【数据范围】

$1\le x_1,C,k\le 9999$。