Circle Game

There are \(n\) kids (numbered from \(0\) to \(n-1\)) sitting in a circle. The positions around the circle are numbered in clockwise order from \(0\) to \(n-1\). Initially, kid \(i\) sits at position \(i\). In each round, every kid moves from their current position \(p\) to position \((p + m) \mod n\). After \(10^k\) rounds, determine the final position of the kid numbered \(x\).

Explanation: Since every round shifts all kids by \(m\) positions (modulo \(n\)), after one round, a kid initially at position \(p\) goes to \((p + m) \mod n\). Therefore, after \(10^k\) rounds, the kid originally at position \(x\) moves to \((x + m \times 10^k) \mod n\). To compute \(10^k\) efficiently when \(k\) might be large, modular exponentiation should be used.

inputFormat

The input consists of four integers separated by spaces:

• n: the number of kids and positions.
• m: the number of positions each kid moves per round.
• k: the exponent so that the number of rounds is \(10^k\).
• x: the number of the kid whose final position is to be determined.

Example: 5 1 1 2

outputFormat

Output a single integer representing the final position of kid \(x\) after \(10^k\) rounds.

Example: For input 5 1 1 2, the output is 2.

sample

5 1 1 2

2