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.PrintWriter;
import java.util.Scanner;

/**
 * Created by omar on 11/11/17.
 */
public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        long A = sc.nextLong(), B = sc.nextLong(), n = sc.nextLong(), x = sc.nextLong();
        long[][] first = {{x, 1}, {0, 0}}, second = {{A, 0}, {B, 1}};
        out.println(multiply(first, exp(second, n), first.length)[0][0]);

        out.flush();
        out.close();
    }

    static int MOD = (int)1e9 + 7;
    static long[][] multiply (long[][] A, long[][] B, int n) {
        long[][] res = new long[n][n];
        for (int row = 0; row < n; row++)
            for (int col = 0; col < n; col++) {
                for (int lop = 0; lop < n; lop++) {
                    res[row][col] += (A[row][lop] * B[lop][col] % MOD);
                    if (res[row][col] >= MOD) res[row][col] -= MOD;
                }
            }
        return res;
    }
    static long[][] identity (int n) {
        long[][] res = new long[n][n];
        for (int i = 0; i < n; i++)
            res[i][i] = 1;
        return res;
    }
    static long[][] exp (long[][] M, long p) {
        if (p == 0) return identity(M.length);
        if (p == 1) return M;
        if (p % 2 == 0) return exp(multiply(M, M, M.length), p >> 1L);
        else return multiply(M, exp(multiply(M, M, M.length), p >> 1L), M.length);
    }
}