你站在一个巨大的、完美的圆形竞技场墙边，将网球用力掷向竞技场的其他部位。在经过给定次数的弹跳后，网球下一次会击中墙壁的什么位置？

将竞技场映射为以原点为中心的单位圆，你站在点 $(-1, 0)$ 处。你掷球的方向由坐标平面上的斜率（一个有理分数 $a/b$）给出。每一次弹跳都是完美的，没有能量损失，且球从墙壁反弹时的反射角等于入射角（相对于碰撞点的切线）。

在经过 $n$ 次弹跳后，球再次击中圆周上的某一点 $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$ 的整数。换句话说，输出一个整数 $k$，满足 $0 \le k < M$ 且 $k \cdot s \equiv r \pmod M$。

例如，如果我们以斜率 $1/2$ 掷球，球弹跳一次，它首先击中墙壁的坐标为 $(3/5, 4/5)$。反弹后，它下一次击中墙壁的坐标为 $(7/25, -24/25)$。$25$ 对素数 $M$ 的模逆元为 $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$ 互质。

输出格式

输出如上所述的单个整数值。

样例

样例输入 1

1 1 3

样例输出 1

1000000006

样例输入 2

1 2 1

样例输出 2

960000007

说明

注意样例 2 对应题目描述中的例子。

样例输入 3

11 63 44

样例输出 3

22

样例输入 4

163 713 980

样例输出 4

0