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;

/**
 * Created by vikas.k on 16/03/17.
 */
public class EC013D {
    public static PrintWriter out;
    public static FastScanner in;
    private int mod = 1000000007;
    private void solve(){
        long A = in.nextLong();
        long B = in.nextLong();

        long n = in.nextLong();
        long x = in.nextLong();

        if(A>1){
            long s = fastExpo(A,n);
            long r = fastExpo(A-1,mod-2);

            long ans = (s-1)*B;
            ans%=mod;
            ans*=r;
            ans%=mod;
            s*=x;
            s%=mod;
            out.print((ans+s)%mod);
        }else{
            long s = ((n%mod)*B)%mod;
            out.print((x+s)%mod);
        }
    }

    private long fastExpo(long a ,long b){
        long ret = 1;
        while(b>0){
            if(b%2 == 1){
                ret = ret*a;
                ret%= mod;
            }
            a = a*a;
            a%=mod;
            b/=2;
        }
        return ret;
    }

    private void runIO(){
        in = new FastScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        solve();
        out.close();
    }
    private static class FastScanner {
        BufferedReader bufferedReader;
        StringTokenizer stringTokenizer;

        private FastScanner(){
            bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        }

        private String next(){
            if(stringTokenizer == null || !stringTokenizer.hasMoreElements()){
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return stringTokenizer.nextToken();
        }

        private int nextInt(){
            return Integer.parseInt(next());
        }
        private long nextLong(){
            return Long.parseLong(next());
        }
        private String nextLine(){
            String ret= "";
            try {
                ret= bufferedReader.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return ret;
        }
    }

    public static void main(String[] args) {
        new EC013D().runIO();
    }
}
