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>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
inline void read(int &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = 10 * x + c - '0';
    c = getchar();
  }
  x *= f;
}
void printDouble(double x, int n) {
  cout << fixed << setprecision(n);
  cout << x << endl;
}
const long long mod = 1000000007;
long long e(long long x, long long y) {
  if (y == 1) return x;
  if (y % 2 == 1) return (x * e(x, y - 1)) % mod;
  long long z = e(x, y / 2);
  return (z * z) % mod;
}
long long inverse(long long x) { return e(x, mod - 2); }
int main() {
  long long A, B, n, x;
  cin >> A >> B >> n >> x;
  long long t = e(A, n);
  if (A == 1) {
    cout << (x + (n % mod * B) % mod) % mod;
    return 0;
  }
  long long C = ((((t - 1) * inverse(A - 1)) % mod) * B) % mod;
  cout << ((t * x) % mod + C) % mod;
}
