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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Aeroui
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public static long xx;
        public static long y;
        public static long gcd;
        private long MOD = (long) 1e9 + 7;

        public void solve(int testNumber, Scanner in, PrintWriter out) {
            long A = in.nextLong();
            long B = in.nextLong();
            long n = in.nextLong();
            long x = in.nextLong();
            gcd(A - 1, MOD);
            while (y < 0) y += A - 1;
            while (xx < 0) xx += MOD;
            long pow = pow(A, n);
            long sum = A == 1 ? mod(n) : mod(pow - 1 + MOD) * xx;

            long ans = mod(mul(x, mod(pow))); // A^n * x
            long spa = mod(mul(sum, B)); // Sum(A^i) * B


            ans = mod(sum(ans, spa));
            out.println(ans);
        }

        long mul(long a, long b) {
            return mod(mod(a) * mod(b));
        }

        long sum(long a, long b) {
            return mod(mod(a) + mod(b));
        }

        public long mod(long n) {
            return n % MOD;
        }

        long pow(long a, long n) {
            if (a == 1)
                return a;
            if (n == 0)
                return 1;
            if (n == 1)
                return mod(a);

            long p = pow(a, n / 2);
            p = mod(mul(p, p));
            if (n % 2l == 1l)
                p = mod(mul(p, a));
            return mod(p);
        }

        public static void gcd(long a, long b) {

            if (b == 0) {
                y = 0;
                xx = 1;
                gcd = a;
            } else {
                gcd(b, a % b);
                long temp = xx;
                xx = y;
                y = temp - (a / b) * y;
            }
        }

    }
}

