Consider 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 109 + 7.

Input

The only line contains four integers A, B, n and x (1 ≤ A, B, x ≤ 109, 1 ≤ n ≤ 1018) — 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 109 + 7.

Examples

Input

3 4 1 1


Output

7


Input

3 4 2 1


Output

25


Input

3 4 3 1


Output

79
import java.util.Scanner;

// Gn = A *Gn-1 + B
// G0 = x
public class D {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long A = sc.nextLong();
        long B = sc.nextLong();
        long n = sc.nextLong();
        long x = sc.nextLong();
        long mod = 1000000007;
        long res = 0;

        long[][] trans = { { A, B }, { 0, 1 } };
        long[][] init = { { x }, { 1 } };
        long[][] sum = powQuick(trans, n, mod);
        res = mul(sum, init, mod)[0][0] % mod;

        System.out.println(res);
    }

    // quick matrix power
    private static long[][] powQuick(long[][] mat, long exp, long mod) {
        long[][] ans = identityMatrix(mat.length);

        long[][] power = copy(mat);
        while (exp != 0) {
            if ((exp & 1) != 0)
                ans = mul(ans, power, mod);
            power = mul(power, power, mod);
            exp >>= 1;
        }
        return ans;
    }

    private static long[][] identityMatrix(int n) {
        long[][] I = new long[n][n];
        for (int i = 0; i < n; i++) {
            I[i][i] = 1;
        }
        return I;
    }

    private static long[][] copy(long[][] a) {
        int M = a.length;
        int N = a[0].length;
        long[][] ans = new long[M][N];
        for (int i = 0; i < M; i++)
            for (int j = 0; j < N; j++)
                ans[i][j] = a[i][j];
        return ans;
    }

    // matrix multiply
    // a: MxN, b:NxL, return MxL
    private static long[][] mul(long[][] a, long[][] b, long mod) {
        int M = a.length;
        int N = a[0].length;
        int L = b[0].length;

        long[][] ans = new long[M][L];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < L; j++) {
                for (int k = 0; k < N; k++) {
                    ans[i][j] += (a[i][k] * b[k][j]) % mod;
                }
            }
        }
        return ans;
    }

}