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
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T abs(T t) {
  return t < 0 ? -t : t;
}
const long long modn = 1000000007;
inline long long mod(long long x) { return x % modn; }
const int MAXN = 2;
long long A, B, x, n, k;
long long m[MAXN][MAXN], base[MAXN][MAXN], aux[MAXN][MAXN];
int s[MAXN];
void expo(long long e) {
  if (e == 1) {
    return;
  }
  expo(e / 2ll);
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      aux[i][j] = 0;
      for (int k = 0; k < 2; k++) {
        aux[i][j] = mod(aux[i][j] + m[k][j] * m[i][k]);
      }
    }
  }
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      m[i][j] = aux[i][j];
      ;
    }
  }
  if (e & 1) {
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        aux[i][j] = 0;
        for (int k = 0; k < 2; k++) {
          aux[i][j] = mod(aux[i][j] + m[k][j] * base[i][k]);
        }
      }
    }
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        m[i][j] = aux[i][j];
      }
    }
  }
}
void printm() {
  for (int a = 0; a < 2; a++) {
    for (int b = 0; b < 2; b++) {
      ;
    };
  }
}
int main() {
  scanf("%lld%lld%lld%lld", &A, &B, &n, &x);
  base[0][0] = A;
  base[0][1] = 1;
  base[1][0] = 0;
  base[1][1] = 1;
  for (int a = 0; a < 2; a++)
    for (int b = 0; b < 2; b++) m[a][b] = base[a][b];
  expo(n);
  printm();
  printf("%lld\n", mod(m[0][0] * x + m[0][1] * B));
}
