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.*;
import java.util.StringTokenizer;

public class Main {

    private boolean useFiles = false;
    private String fileIn = "input.txt";
    private String fileOut = "output.txt";

    public static final long MOD = 1000L * 1000L * 1000L + 7L;

    long[] mul(long a, long b, long a1, long b1) {
        return new long[] { (a * a1) % MOD, (a * b1 + b) % MOD };
    }

    long[] powMat(long a, long b, long p) {
        if (p == 1) return new long[]{a, b};

        long[] subpow = powMat(a, b, p / 2);

        long[] m = mul(subpow[0], subpow[1], subpow[0], subpow[1]);

        if (p % 2 == 1) {
            m = mul(a, b, m[0], m[1]);
        }

        return m;
    }

    void solve() throws IOException {
        long a = nextLong(), b = nextLong(), n = nextLong(), x = nextLong();

        long res[] = powMat(a, b, n);

        System.out.println( (x * res[0] + res[1]) % MOD );
    }

    void run() throws IOException {
        st = new StringTokenizer("");

        if (useFiles) {
            in = new BufferedReader(new FileReader(fileIn));
            out = new PrintWriter(new FileWriter(fileOut));
        } else {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }

        solve();

        in.close();
        out.close();
    }

    StringTokenizer st;
    BufferedReader in;
    PrintWriter out;

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    String nextToken() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}