题目描述

$n$ 个小伙伴（编号 $0$ 到 $n-1$）围坐一圈。初始时编号为 $i$ 的小伙伴坐在位置 $i$。

每轮游戏：位置 $i$ 上的小伙伴顺时针移动 $m$ 步到位置 $(i + m) \bmod n$。

一共进行 $10^k$ 轮，问最初编号为 $x$ 的小伙伴最后在哪个位置。

输入格式

一行四个整数 $n, m, k, x$。

输出格式

一个整数，表示 $10^k$ 轮后 $x$ 号小伙伴的位置编号。

10 3 4 5

5

数据规模与约定

对于全部的测试点，保证 $1 < n < 10^6$，$0 < m < n$，$1 \leq x \leq n$，$0 < k < 10^9$。

本题改编自 NOIP 2013 提高组