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.*;
import static java.lang.Math.*;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Double.parseDouble;
import static java.lang.String.*;

public class Main {
    
    static long MOD = (long)1e9 + 7;
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        StringTokenizer tk;
        
        tk = new StringTokenizer(in.readLine());
        long a = parseLong(tk.nextToken()),b = parseLong(tk.nextToken()),n = parseLong(tk.nextToken()),x = parseLong(tk.nextToken());
        
        long an = pow(a,n);
        
        long p1 = ((an%MOD)*(x%MOD))%MOD;
        long p2 = (an%MOD-1+MOD)%MOD;
        p2 = (p2 * (pow(a-1,MOD-2)%MOD))%MOD;
        if(a==1) p2 = n%MOD;
        long p3 = ((b%MOD)*(p2%MOD))%MOD;
        
        System.out.println((p1+p3)%MOD);
    }
    
    static long pow(long n,long p) {
        if(p==0)
            return 1;
        
        if(p%2l==1l)
            return ((pow(n,p-1)%MOD)*(n%MOD))%MOD;
        
        long r = pow(n,p/2);
        
        return ((r%MOD)*(r%MOD))%MOD;
    }
}
