#include <bits/stdc++.h>
using namespace std;
const long double PI = 3.141592653589793;
const long double E = 2.71828182845904523;
const long long LLINF = 4000000009000000099;
const long long INF = 2009000099;
const long long MOD7 = 1000000007;
const long long MOD9 = 1000000009;
template <class A, class B, class C>
struct triple {
  A first;
  B second;
  C third;
  triple(A, B, C);
  triple();
};
template <class A, class B, class C>
triple<A, B, C>::triple(A a, B b, C c) {
  first = a;
  second = b;
  third = c;
}
template <class A, class B, class C>
triple<A, B, C>::triple() {}
template <class A, class B, class C>
triple<A, B, C> make_triple(A a, B b, C c) {
  triple<A, B, C> t(a, b, c);
  return t;
}
template <class A, class B, class C>
bool operator<(triple<A, B, C> a, triple<A, B, C> b) {
  if (a.first != b.first) return a.first < b.first;
  if (a.second != b.second) return a.second < b.second;
  if (a.third != b.third) return a.third < b.third;
}
template <class T>
T inline sqr(T a) {
  return a * a;
}
long long bpow(long long a, long long d, long long mod) {
  if (d == 0) return 1;
  long long t = bpow(a, d / 2, mod);
  t = (t * t) % mod;
  if (d & 1) t = (t * a) % mod;
  return t;
}
long long bpow(long long a, long long d) {
  if (d == 0) return 1;
  long long t = bpow(a, d / 2);
  t = (t * t);
  if (d & 1) t = (t * a);
  return t;
}
long long gcd(long long a, long long b) {
  while (a && b)
    if (a > b)
      a %= b;
    else
      b %= a;
  return a + b;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long C(long long n, long long k) {
  long long res = 1;
  for (int i = 1; i <= k; ++i) res = res * (n - k + i) / i;
  return res;
}
long long C(long long n, long long k, long long mod) {
  long long u = 1, d = 1;
  for (int i = 2; i <= n; ++i) u = (u * i) % mod;
  int x = max(k, n - k), z = min(k, n - k);
  for (int i = 2; i <= x; ++i) {
    d = (d * i) % mod;
    if (i <= z) d = (d * i) % mod;
  }
  d = bpow(d, mod - 2, mod);
  long long res = (u * d) % mod;
  return res;
}
long long a, b, x, n;
long long f(long long n) {
  if (n == 0) return 1;
  if (n & 1) {
    long long t = bpow(a, n / 2 + 1, MOD7) + 1;
    t *= f(n / 2);
    return t % MOD7;
  } else {
    long long t = bpow(a, n / 2 + 1, MOD7) + 1;
    t *= f(n / 2 - 1);
    t %= MOD7;
    t += bpow(a, n / 2, MOD7);
    return t % MOD7;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> a >> b >> n >> x;
  long long res = x * bpow(a, n, MOD7);
  res %= MOD7;
  res += b * f(n - 1);
  cout << res % MOD7;
}

### Prompt

Your task is to create a CPP solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long double PI = 3.141592653589793;
const long double E = 2.71828182845904523;
const long long LLINF = 4000000009000000099;
const long long INF = 2009000099;
const long long MOD7 = 1000000007;
const long long MOD9 = 1000000009;
template <class A, class B, class C>
struct triple {
  A first;
  B second;
  C third;
  triple(A, B, C);
  triple();
};
template <class A, class B, class C>
triple<A, B, C>::triple(A a, B b, C c) {
  first = a;
  second = b;
  third = c;
}
template <class A, class B, class C>
triple<A, B, C>::triple() {}
template <class A, class B, class C>
triple<A, B, C> make_triple(A a, B b, C c) {
  triple<A, B, C> t(a, b, c);
  return t;
}
template <class A, class B, class C>
bool operator<(triple<A, B, C> a, triple<A, B, C> b) {
  if (a.first != b.first) return a.first < b.first;
  if (a.second != b.second) return a.second < b.second;
  if (a.third != b.third) return a.third < b.third;
}
template <class T>
T inline sqr(T a) {
  return a * a;
}
long long bpow(long long a, long long d, long long mod) {
  if (d == 0) return 1;
  long long t = bpow(a, d / 2, mod);
  t = (t * t) % mod;
  if (d & 1) t = (t * a) % mod;
  return t;
}
long long bpow(long long a, long long d) {
  if (d == 0) return 1;
  long long t = bpow(a, d / 2);
  t = (t * t);
  if (d & 1) t = (t * a);
  return t;
}
long long gcd(long long a, long long b) {
  while (a && b)
    if (a > b)
      a %= b;
    else
      b %= a;
  return a + b;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long C(long long n, long long k) {
  long long res = 1;
  for (int i = 1; i <= k; ++i) res = res * (n - k + i) / i;
  return res;
}
long long C(long long n, long long k, long long mod) {
  long long u = 1, d = 1;
  for (int i = 2; i <= n; ++i) u = (u * i) % mod;
  int x = max(k, n - k), z = min(k, n - k);
  for (int i = 2; i <= x; ++i) {
    d = (d * i) % mod;
    if (i <= z) d = (d * i) % mod;
  }
  d = bpow(d, mod - 2, mod);
  long long res = (u * d) % mod;
  return res;
}
long long a, b, x, n;
long long f(long long n) {
  if (n == 0) return 1;
  if (n & 1) {
    long long t = bpow(a, n / 2 + 1, MOD7) + 1;
    t *= f(n / 2);
    return t % MOD7;
  } else {
    long long t = bpow(a, n / 2 + 1, MOD7) + 1;
    t *= f(n / 2 - 1);
    t %= MOD7;
    t += bpow(a, n / 2, MOD7);
    return t % MOD7;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> a >> b >> n >> x;
  long long res = x * bpow(a, n, MOD7);
  res %= MOD7;
  res += b * f(n - 1);
  cout << res % MOD7;
}

```