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
/**
 * Created by zinov on 13.06.2016.
 */

import java.util.*;
import java.io.*;

public class D {
    final long MOD = 1000000007;

    long pow(long a, long d) {
        if (d == 0)
            return 1;
        long ret = pow(a, d / 2);
        ret *= ret;
        ret %= MOD;
        if (d % 2 == 1)
            ret = (ret * a) % MOD;

        return ret;
    }

    long inv(long a) {
        return pow(a, MOD - 2);
    }

    public void solve() throws IOException {
        long A, B, n, x;
        A = nextLong();
        B = nextLong();
        n = nextLong();
        x = nextLong();

        long answ;
        if (A != 1) {
            answ = ((pow(A, n) * x) % MOD + ((B * (pow(A, n) - 1)) % MOD) * inv(A - 1) % MOD) % MOD;
        }
        else {
            answ = (x + n % MOD * B % MOD) % MOD;
        }
        output.print(answ);
    }

    public BufferedReader input;
    public PrintWriter output;
    public StringTokenizer stringTokenizer = new StringTokenizer("");

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

    D() throws IOException {
        input = new BufferedReader(new InputStreamReader(System.in));
        output = new PrintWriter(System.out);
        solve();
        input.close();
        output.close();
    }

    public String next() throws IOException {
        while (!stringTokenizer.hasMoreTokens() || stringTokenizer == null)
            stringTokenizer = new StringTokenizer(input.readLine());

        return stringTokenizer.nextToken();
    }

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

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

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