题目描述

小 Y 家有一个智能密码锁，密码是 $0 \sim 9999$ 的一个整数。这个密码锁的特殊之处在于：假设当前密码为 $x$，用密码开一次门之后，密码就会变成 $x^2 + C$ 对 $10000$ 取余的结果，其中 $C$ 是用户事先设定的常数。\n\n小 Y 忘记了当前密码，但记得初始密码 $x_1$ 和设定的常数 $C$，以及这是他第 $k$ 次开门。请帮他计算第 $k$ 次开门时的密码。

输入格式

输入一行三个正整数 $x_1, C, k$，分别表示初始密码、常数 $C$ 和第几次开门。

输出格式

输出一行一个自然数，表示第 $k$ 次开门时的密码。

样例

1000 3 1

1000

1000 3 2

3

1000 3 3

12

提示

样例解释\n\n初始密码为 $1000$，$C = 3$。\n\n第 $1$ 次开门的密码就是初始密码 $1000$。\n第 $1$ 次开门后，密码变为 $(1000^2 + 3) \bmod 10000 = 3$，所以第 $2$ 次开门的密码为 $3$。\n第 $2$ 次开门后，密码变为 $(3^2 + 3) \bmod 10000 = 12$，所以第 $3$ 次开门的密码为 $12$。\n\n### 数据规模与约定\n\n$1 \leq x_1, C, k \leq 9999$。