Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Iterated Linear Function

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputConsider a linear function *f*(*x*) = *Ax* + *B*. Let's define *g*^{(0)}(*x*) = *x* and *g*^{(n)}(*x*) = *f*(*g*^{(n - 1)}(*x*)) for *n* > 0. For the given integer values *A*, *B*, *n* and *x* find the value of *g*^{(n)}(*x*) modulo 10^{9} + 7.

Input

The only line contains four integers *A*, *B*, *n* and *x* (1 ≤ *A*, *B*, *x* ≤ 10^{9}, 1 ≤ *n* ≤ 10^{18}) — the parameters from the problem statement.

Note that the given value *n* can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.

Output

Print the only integer *s* — the value *g*^{(n)}(*x*) modulo 10^{9} + 7.

Examples

Input

3 4 1 1

Output

7

Input

3 4 2 1

Output

25

Input

3 4 3 1

Output

79

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/16/2017 00:50:22 (c6).

Desktop version, switch to mobile version.

User lists

Name |
---|