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

public class Solution {
    
    public static long mod = 1000000007;
 
    public static long fun(long A, long n)
    {
        long result = 1;
        
        while(n>0)
        {
        if(n%2==1)
            result = (result%mod * A%mod)%mod;
            
            A =  (A%mod * A%mod)%mod;
            n /= 2;
        }
        return result%mod;
    }
    
    
 public static void main(String[] args) throws IOException{

     
     
    // BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
     PrintWriter  pw = new PrintWriter(System.out);
     Scanner in = new Scanner(System.in);
   
     
     long A = in.nextLong();
     long B = in.nextLong();
     long n = in.nextLong();
     long x = in.nextLong();
     
     
       long w =fun(A,n);
		long t = fun(A-1,mod-2);
		long ans = t*(w-1)%mod * B%mod ;
		ans = (ans + w*x)%mod;
    // mul3 %= mod;
  
     if(A==1) {
         long T =(n%mod*B%mod+x%mod)%mod ; 
		  pw.print(T);
     }      
         else 
            pw.println(ans);


     
     
  
     pw.flush();
     pw.close();
     
   }
}
