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.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Iteratedlinear {

	private static long MOD=(long) (1e9+7);
	public static void main(String[] args)
	{
		// TODO Auto-generated method stub
		MyScanneril sc=new MyScanneril();
		long a=sc.nextLong();
		long b=sc.nextLong();
		long n=sc.nextLong();
		long x=sc.nextLong();
		
		
	if(a!=1){
		long result=(fastexp(a,n)*x)%MOD;
		//System.out.println(result);
		long res=(fastexp(a,n)-1)*fastexp((a-1),MOD-2);
		res=res%MOD;
		res=(res*b)%MOD;
		
		result=(result+res)%MOD;
		
		System.out.println(result);
	}
	else
	{
		long result=((n%MOD)*b)%MOD;
		result=(result+x)%MOD;
		System.out.println(result);
	}
		
	}
	public static long fastexp(long base,long exp)
	{
		long result=1;
		while(exp>0)
		{
			if(exp%2==1)
				result=(result*base)%MOD;
			base=(base*base)%MOD;
			exp=exp/2;
			
		}
		return result;
	}

}
class MyScanneril
{
	BufferedReader br;
	StringTokenizer st;
	MyScanneril()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}
	String next()
	{
		
		while(st==null || !st.hasMoreTokens())
		{
			try
			{
				st=new StringTokenizer(br.readLine());
			}
			catch(Exception e)
			{
				e.printStackTrace();
			}
		}
		return st.nextToken();
		
	}
	int nextInt()
	{
		return Integer.parseInt(next());
	}
	long nextLong()
	{
		return Long.parseLong(next());
	}
	double nextDouble()
	{
		return Double.parseDouble(next());
	}
	String nextLine()
	{
		String str="";
		try
		{
			str=br.readLine();
		}
		catch(Exception e)
		{
			e.printStackTrace();
		}
		return str;
		
	}
}