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

public class D678 {

    public static BufferedReader read = null;
    public static PrintWriter out = null;
    public static StringTokenizer token = null;

    public static long powmod(long a, long b, long m)
    {
        if(b == 0) return 1;
        if(b == 1) return a % m;
        long c = powmod(a, b/2, m);
        c = c * c  % m;
        if(b % 2 == 1) c = c * a % m;
        return c % m;
    }
    public static void solve()
    {
        long mod = 1000000000+7;
        long A = nlong(), B = nlong(), n = nlong(), x = nlong();
        if(A == 1)
        {
            n%=mod;
            out.println((x + (B * n % mod)) % mod);
            return;
        }
        long ans = powmod(A, n, mod) * x % mod;
        long t1 = (powmod(A, n, mod) - 1 + mod) % mod;
        long t2 = powmod(A-1, mod-2, mod);
        t1 = t1 * t2 % mod;
        t1 = t1 * B % mod;
        ans += t1;
        ans%=mod;
        out.println(ans);


    }

    public static void main(String[] args)
    {
        read = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.flush();
        out.close();

    }

    // i/o functions
    public static String next() // returns the next string
    {
        while(token == null || !token.hasMoreTokens())
        {
            try {
                token = new StringTokenizer(read.readLine());
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        return token.nextToken();
    }

    public static int nint()
    {
        return Integer.parseInt(next());
    }
    public static long nlong()
    {
        return Long.parseLong(next());
    }
    public static double ndouble()
    {
        return Double.parseDouble(next());
    }
    public static int[] narr(int n)
    {
        int[] a = new int[n];
        for(int i=0; i<n; i++) a[i] = nint();
        return a;
    }

    public static long[] nal(int n)
    {
        long[] a = new long[n];
        for(int i=0; i<n; i++) a[i] = nlong();
        return a;
    }


}


