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.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.io.*;

public class B 
{
	public static void main(String[] args)
	{
		new B().solve();
	}

	FasterScanner in=new FasterScanner();
	PrintWriter out=new PrintWriter(System.out);
	
	long mod=(int)1e9+7;
	public void solve()
	{
		long a = in.nextLong(), b = in.nextLong();
		long n=in.nextLong();
		long x=in.nextLong();
		long[][] mat = {{a,0,b},{1,0,0},{0,0,1}};
		mat = matpow(mat,n);
		long [][] ans= { {x} ,{0} , {1} };
		ans = matrixMul(mat, ans);
		out.println(ans[0][0]);;
		out.close();
	}
	
	long[][] matpow(long[][] mat,long pow)
	{
		String bin = Long.toBinaryString(pow);
		long[][] ans = new long[mat.length][mat.length];
		for(int i=0;i<mat.length;i++)
			ans[i][i]=1;
		for(int i=0;i<bin.length();i++)
		{
			ans = matrixMul(ans, ans);
			if(bin.charAt(i)=='1')
			{
				ans = matrixMul(ans, mat);
			}
		}
		return ans;
	}
	
	long[][] matrixMul(long[][] a , long[][] b)
	{
		long[][] ans = new long[a.length][b[0].length];
		
		for(int i=0;i<a.length;i++)
		{
			for(int j=0;j<b[0].length;j++)
			{
				for(int k=0;k<a[0].length;k++)
				{
					ans[i][j] += (a[i][k]*b[k][j])%mod;
					ans[i][j] %= mod;
				}
			}
		}
		
		return ans;
	}
	
	private long gcd(long a, long b) {
		if(a<b)
			return gcd(b,a);
		if(b==0)
			return a;
		return gcd(b,a%b);
	}

	public static class SegmentTree2D {
		  public static int max(int[][] t, int x1, int y1, int x2, int y2) {
		    int n = t.length >> 1;
		    x1 += n;
		    x2 += n;
		    int m = t[0].length >> 1;
		    y1 += m;
		    y2 += m;
		    int res = Integer.MIN_VALUE;
		    for (int lx = x1, rx = x2; lx <= rx; lx = (lx + 1) >> 1, rx = (rx - 1) >> 1)
		      for (int ly = y1, ry = y2; ly <= ry; ly = (ly + 1) >> 1, ry = (ry - 1) >> 1) {
		        if ((lx & 1) != 0 && (ly & 1) != 0) res = Math.max(res, t[lx][ly]);
		        if ((lx & 1) != 0 && (ry & 1) == 0) res = Math.max(res, t[lx][ry]);
		        if ((rx & 1) == 0 && (ly & 1) != 0) res = Math.max(res, t[rx][ly]);
		        if ((rx & 1) == 0 && (ry & 1) == 0) res = Math.max(res, t[rx][ry]);
		      }
		    return res;
		  }

		  public static void add(int[][] t, int x, int y, int value) {
		    x += t.length >> 1;
		    y += t[0].length >> 1;
		    t[x][y] += value;
		    for (int tx = x; tx > 0; tx >>= 1)
		      for (int ty = y; ty > 0; ty >>= 1) {
		        if (tx > 1) t[tx >> 1][ty] = Math.max(t[tx][ty], t[tx ^ 1][ty]);
		        if (ty > 1) t[tx][ty >> 1] = Math.max(t[tx][ty], t[tx][ty ^ 1]);
		      }

//		    for (int ty = y; ty > 1; ty >>= 1)
//		      t[x][ty >> 1] = Math.max(t[x][ty], t[x][ty ^ 1]);
//		    for (int tx = x; tx > 1; tx >>= 1)
//		      for (int ty = y; ty > 0; ty >>= 1)
//		        t[tx >> 1][ty] = Math.max(t[tx][ty], t[tx ^ 1][ty]);

//		    for (int lx=x; lx> 0; lx >>= 1) {
//		      if (lx > 1)
//		        t[lx >> 1][y] = Math.max(t[lx][y], t[lx ^ 1][y]);
//		      for (int ly = y; ly > 1; ly >>= 1)
//		        t[lx][ly >> 1] = Math.max(t[lx][ly], t[lx][ly ^ 1]);
//		    }
		  }
	}

	public long pow(long x,long p)
	{
		return pow(x,Long.toBinaryString(p));
	}
	
	public long pow(long x,String pow)
	{
		long ans=1;
		
		for(int i=0;i<pow.length();i++)
		{
			ans*=ans;
			ans%=mod;
			if(pow.charAt(i)=='1')
			{
				ans*=x;
				ans%=mod;
			}
		}
		return ans;
	}
	
	int[][] arr; 
	int[][] visit;
	int[] ans;
	int cur;

	void dfs(int x,int y)
	{
		try
		{
			if(x<0 || x>=arr.length || y<0 || y>=arr[0].length)
			{
				return;
			}
			if(arr[x][y]==0)
			{
				return;
			}
			if(visit[x][y]!=0)
			{
				return;
			}

			visit[x][y]=cur;
			ans[cur]++;

			dfs(x-1,y-1);
			dfs(x-1,y);
			dfs(x-1,y+1);
			dfs(x,y-1);
			dfs(x,y+1);
			dfs(x+1,y-1);
			dfs(x+1,y);
			dfs(x+1,y+1);
		}
		catch(Exception e)
		{
			return ;
		}
	}


	class Edge
	{
		int nextv;
		int r;
		int t;
		public Edge(int ver,int r,int t)
		{
			this.nextv=ver;
			this.r=r;
			this.t=t;
		}
	}

	class s implements Comparable<s>
	{
		int idx;
		int w;
		public s(int i)
		{
			this.idx=i;
			this.w=Integer.MAX_VALUE;
		}

		@Override
		public int compareTo(s o) {
			// TODO Auto-generated method stub
			if(this.w!=o.w)
				return Integer.compare(this.w, o.w);
			else
				return Integer.compare(this.idx, o.idx);
		}
	}

	public static class FasterScanner {
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = System.in.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
		private boolean isEndOfLine(int c) {
			return c=='\n' || c=='\r' || c==-1;
		}
		public String nextString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
		private boolean isSpaceChar(int c) {
			return c=='\n' || c=='\r' || c==-1 || c==' ' || c=='\t';
		}
		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}

			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public double nextDouble()
		{
			return Double.parseDouble(nextString());
		}
		public int[] nextIntArray(int n)
		{
			int[] arr=new int[n];
			for(int i=0;i<n;i++)
			{
				arr[i]=nextInt();
			}
			return arr;
		}
		public long[] nextLongArray(int n)
		{
			long[] arr=new long[n];
			for(int i=0;i<n;i++)
			{
				arr[i]=nextLong();
			}
			return arr;
		}
		public int[] nextIntArray10(int n)
		{
			int[] arr=new int[n+1];
			for(int i=1;i<=n;i++)
			{
				arr[i]=nextInt();
			}
			return arr;
		}
		public long[] nextLongArray10(int n)
		{
			long[] arr=new long[n+1];
			for(int i=1;i<=n;i++)
			{
				arr[i]=nextLong();
			}
			return arr;
		}
		public int[] nextIntArray11(int n)
		{
			int[] arr=new int[n+2];
			for(int i=1;i<=n;i++)
			{
				arr[i]=nextInt();
			}
			return arr;
		}
		public long[] nextLongArray11(int n)
		{
			long[] arr=new long[n+2];
			for(int i=1;i<=n;i++)
			{
				arr[i]=nextLong();
			}
			return arr;
		}
	}

}