원에서의 공 튕기기

넓고 완벽한 원형 경기장의 벽 옆에 서서 테니스 공을 경기장의 다른 부분을 향해 세게 던진다. 정해진 횟수만큼 튕긴 뒤, 테니스 공은 벽의 어느 지점에 다음으로 부딪히는가?

경기장을 원점이 중심인 단위원으로 나타내고, 당신은 점 $(-1, 0)$에 서 있다. 공은 좌표평면에서 유리수 $a/b$로 주어지는 기울기 방향으로 던진다. 각 튕김은 완벽해서 에너지를 잃지 않으며, 충돌 지점에서 벽에 접하는 접선을 기준으로 입사각과 반사각이 같게 튕긴다.

$n$번 튕긴 뒤, 공은 원 위의 어떤 점 $p$에 다시 부딪히며, $p$의 좌표는 $(r/s, t/u)$로 나타낼 수 있는 유리수이다. 분수 $r/s$를 소수 $M = 1{,}000{,}000{,}007$로 나눈 나머지를 출력하라.

$x$ 좌표는 기약분수 $r/s$로 나타낼 수 있음이 알려져 있으며, 여기서 $r$과 $s$는 정수이고 $s \not\equiv 0 \pmod M$이다. $r\cdot s^{-1} \pmod M$과 같은 정수를 출력하라. 즉, $0 \le k < M$이고 $k\cdot s \equiv r \pmod M$인 정수 $k$를 출력하라.

예를 들어, 기울기 $1/2$로 공을 던져 한 번 튕기면, 처음에는 좌표 $(3/5, 4/5)$에서 벽에 부딪힌다. 튕긴 뒤에는 다음으로 좌표 $(7/25, -24/25)$에서 벽에 부딪힌다. 소수 $M$에 대한 $25$의 모듈로 역원은 $280{,}000{,}002$이고, 최종 결과는 $7\cdot 280{,}000{,}002 \pmod M = 960{,}000{,}007$이다.

입력의 한 줄에 세 정수 $a$, $b$ ($1 \le a,b \le 10^9, \gcd(a,b)=1$)와 $n$ ($1 \le n \le 10^{12}$)이 주어지며, $a/b$는 던진 방향의 기울기이고 $n$은 튕긴 횟수이다. $a$와 $b$는 서로소이다.

위에서 설명한 대로 정수 하나를 출력한다.

예제 2는 문제 설명의 예시에 해당한다.