Smart Password Lock

At Xiao Y's house, there is an intelligent password lock. The password is an integer in the range \(0 \sim 9999\). Unlike a traditional lock, after using the current password \(x\) to open the door, the lock updates its password to \( (x^2 + C) \bmod 10000 \), where \(C\) is a fixed constant set by the user.

You are given the initial password \(x_1\), the constant \(C\), and a number \(k\) indicating the door opening attempt. The password used on the first opening is \(x_1\) and then for each successive opening the new password is computed using the recurrence \(a_{i+1} = (a_i^2 + C) \bmod 10000\). Compute the password used for the \(k\)-th door opening.

inputFormat

The input consists of three integers \(x_1\), \(C\), and \(k\) separated by spaces.

Constraints:

• \(0 \le x_1 \le 9999\)
• \(0 \le C \le 10^9\)
• \(1 \le k \le 10^9\)

outputFormat

Output a single integer — the password used on the \(k\)-th door opening.

sample

123 456 1

123