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.*;

public class Equal {

	static ArrayList<Integer>[] adj;

	static boolean check(int[] arr) {
		boolean f = true;
		for (int i = 1; i < arr.length; i++) {
			f &= arr[i] >= arr[i - 1];
		}
		return f;
	}

	public static void main(String[] args) throws IOException {
		// BufferedReader br = new BufferedReader(new FileReader("name.in"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		PrintWriter pw = new PrintWriter(System.out);

		st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		long n = Long.parseLong(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
		
		int[][] mat = new int[][] { { a, 1 }, { 0, 1 } };

		int[][] end = new int[2][1];
		end[0][0] = x;
		end[1][0] = b;
		int[][] temp = matPow(mat, n);
//		System.out.println(Arrays.deepToString(mat));
//		System.out.println(Arrays.deepToString(temp));
		pw.println(matMul(temp, end, 2, 2, 1)[0][0]);

		pw.flush();

	}

	static int mod = 1000000007;

	static int[][] matMul(int[][] A, int[][] B, int p, int q, int r) // C(p x r) = A(p x q) x (q x r) -- O(p x q x r)
	{
		int[][] C = new int[p][r];
		for (int i = 0; i < p; ++i)
			for (int j = 0; j < r; ++j)
				for (int k = 0; k < q; ++k) {
					C[i][j] += (A[i][k] * 1l * B[k][j]) % mod;
					C[i][j] %= mod;
				}
		return C;
	}

	/*
	 * 4. Square Matrix Exponentiation
	 */
	static int[][] matPow(int[][] base, long p) {
		int n = base.length;
		int[][] ans = new int[n][n];
		for (int i = 0; i < n; i++)
			ans[i][i] = 1;
		while (p != 0) {
			if ((p & 1) == 1)
				ans = matMul(ans, base, n, n, n);
			base = matMul(base, base, n, n, n);
			p >>= 1;
		}

		return ans;
	}

	static long powmod(long r, long e, long mod) {
		long ans = 1;
		r %= mod;
		while (e > 0) {
			if ((e & 1) == 1)
				ans = (int) ((ans * 1l * r) % mod);
			e >>= 1;
			r = (int) ((r * 1l * r) % mod);
		}
		return ans;
	}

	static class SegmentTree { // 1-based DS, OOP

		int N; // the number of elements in the array as a power of 2 (i.e. after padding)
		int[] array, sTree, lazy;

		SegmentTree(int[] in, int s) {
			array = in;
			N = in.length - 1;
			sTree = new int[N << 1]; // no. of nodes = 2*N - 1, we add one to cross out index zero
			lazy = new int[N << 1];
			build(1, 1, N, s);
		}

		void build(int node, int b, int e, int s) // O(n)
		{
			if (b == e)
				sTree[node] = array[b];
			else {
				int mid = b + e >> 1;
				build(node << 1, b, mid, s);
				build(node << 1 | 1, mid + 1, e, s);
				if (s == 0) {
					sTree[node] = Math.max(sTree[node << 1], sTree[node << 1 | 1]);
				} else {
					sTree[node] = Math.min(sTree[node << 1], sTree[node << 1 | 1]);

				}
			}
		}

		void update_point(int node, int val, int s) // O(log n)
		{
			node += N - 1;
			sTree[node] += val;
			while (node > 1) {
				node >>= 1;
				if (s == 0) {
					sTree[node] = Math.max(sTree[node << 1], sTree[node << 1 | 1]);
				} else {
					sTree[node] = Math.min(sTree[node << 1], sTree[node << 1 | 1]);

				}
			}
		}

		void update_range(int i, int j, int val) // O(log n)
		{
			update_range(1, 1, N, i, j, val);
		}

		void update_range(int node, int b, int e, int i, int j, int val) {
			if (i > e || j < b)
				return;
			if (b >= i && e <= j) {
				sTree[node] += (e - b + 1) * val;
				lazy[node] += val;
			} else {
				int mid = b + e >> 1;
				propagate(node, b, mid, e);
				update_range(node << 1, b, mid, i, j, val);
				update_range(node << 1 | 1, mid + 1, e, i, j, val);
				sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
			}

		}

		void propagate(int node, int b, int mid, int e) {
			lazy[node << 1] += lazy[node];
			lazy[node << 1 | 1] += lazy[node];
			sTree[node << 1] += (mid - b + 1) * lazy[node];
			sTree[node << 1 | 1] += (e - mid) * lazy[node];
			lazy[node] = 0;
		}

		int query(int i, int j, int s) {
			return query(1, 1, N, i, j, s);
		}

		int query(int node, int b, int e, int i, int j, int s) // O(log n)
		{
			if (i > e || j < b) {
				if (s == 0)
					return 0;
				return Integer.MAX_VALUE / 2;
			}
			if (b >= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
			propagate(node, b, mid, e);
			int q1 = query(node << 1, b, mid, i, j, s);
			int q2 = query(node << 1 | 1, mid + 1, e, i, j, s);
			if (s == 0)
				return Math.max(q1, q2);
			else
				return Math.min(q1, q2);

		}

	}

	static class pair implements Comparable<pair> {
		int x;
		int y;

		public pair(int d, int u) {
			x = d;
			y = u;
		}

		@Override
		public int compareTo(pair o) {
			// TODO Auto-generated method stub
			return y - o.y;
		}

		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return x + " " + y;
		}

	}

}