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 com.sun.org.apache.xml.internal.utils.StringComparable;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.*;

public class Main {
    public static void main(String[] args) {
//     Test.testing();
        ConsoleIO io = new ConsoleIO();
        new Main(io).solve();
        io.close();
    }

    ConsoleIO io;

    Main(ConsoleIO io) {
        this.io = io;
    }

    ArrayList<ArrayList<Integer>> gr;
    boolean[] visit;

    class Edge {
        public Edge(int u, double v, int c) {
            this.u = u;
            this.v = v;
            this.c = c;
        }

        public int u;
        public double v;
        public int c;
    }

    long MOD = 1_000_000_007;
    int N, M, K;
    int[][] map;

    public void solve() {
long[] l = io.readLongArray();
        long A = l[0], B = l[1], n = l[2], x = l[3];
        long p = pow(A, n);

        long t= n%MOD;
        if(A!=1){
            t = (div(p, (A-1+MOD)%MOD) - div(1, (A-1+MOD)%MOD) + MOD) % MOD;
        }
        long res = (p*x+B*t)%MOD;
        io.writeLine(res +"");
    }

    long div(long a, long b) {
        return (a * pow(b, MOD - 2)) % MOD;
    }

    long pow(long a, long p) {
        long res = 1;
        while (p > 0) {
            if (p % 2 == 1) res = (res * a) % MOD;
            a = (a * a) % MOD;
            p /= 2;
        }
        return res;
    }

    long gcd(long a, long b) {
        if (a < b) return gcd(b, a);
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

class ConsoleIO {
    BufferedReader br;
    PrintWriter out;
    public ConsoleIO(){br = new BufferedReader(new InputStreamReader(System.in));out = new PrintWriter(System.out);}
    public void flush(){this.out.flush();}
    public void close(){this.out.close();}
    public void writeLine(String s) {this.out.println(s);}
    public void writeInt(int a) {this.out.print(a);this.out.print(' ');}
    public void writeWord(String s){
        this.out.print(s);
    }
    public int read(char[] buf, int len){try {return br.read(buf,0,len);}catch (Exception ex){ return -1; }}
    public String readLine() {try {return br.readLine();}catch (Exception ex){ return "";}}
    public long readLong() {
        return Long.parseLong(this.readLine());
    }
    public int readInt() {
        return Integer.parseInt(this.readLine().trim());
    }
    public long[] readLongArray() {
        String[]n=this.readLine().trim().split("\\s+");long[]r=new long[n.length];
        for(int i=0;i<n.length;i++)r[i]=Long.parseLong(n[i]);
        return r;
    }
    public int[] readIntArray() {
        String[]n=this.readLine().trim().split("\\s+");int[]r=new int[n.length];
        for(int i=0;i<n.length;i++)r[i]=Integer.parseInt(n[i]);
        return r;
    }
    public int[] readIntArray(int n) {
        int[] res = new int[n];
        char[] all = this.readLine().toCharArray();
        int cur = 0;boolean have = false;
        int k = 0;
        boolean neg = false;
        for(int i = 0;i<all.length;i++){
            if(all[i]>='0' && all[i]<='9'){
                cur = cur*10+all[i]-'0';
                have = true;
            }else if(all[i]=='-') {
                neg = true;
            }
            else if(have){
                res[k++] = neg?-cur:cur;
                cur = 0;
                have = false;
                neg = false;
            }
        }
        if(have)res[k++] = neg?-cur:cur;
        return res;
    }
    public void writeIntArray(int[] a) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < a.length; i++) {if (i > 0) sb.append(' ');sb.append(a[i]);}
        this.writeLine(sb.toString());
    }
}
class Pair {
    public Pair(int a, int b) {this.a = a;this.b = b;}
    public int a;
    public int b;
}
class PairLL {
    public PairLL(long a, long b) {this.a = a;this.b = b;}
    public long a;
    public long b;
}



