/*  -*- coding: utf-8 -*-
 *
 * 3052.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const long long MOD = 1000000007LL;

/* typedef */

typedef long long ll;

/* global variables */

/* subroutines */

/* main */

int main() {
  ll a, b, x;
  scanf("%lld%lld%lld", &a, &b, &x);

  ll sum = x % MOD;
  if (x >= a) {
    ll k = (x - a) / (a - b) + 1;
    sum = (sum + (k % MOD) * (b % MOD)) % MOD;
  }

  printf("%lld\n", sum);
  return 0;
}


### Prompt

Construct a CPP code solution to the problem outlined:

Problem

If you bring an empty bottle of $ a $ milk, you can exchange it for a new bottle of $ b $ milk.
How many bottles of milk can Mr. Kawabayashi, who initially has a bottle of $ x $ milk, drink? Output the remainder after dividing by $ 1000000007 $.

Constraints

The input satisfies the following conditions.

* $ 1 \ leq a \ leq 10 ^ {15} $
* $ 0 \ leq b \ lt a $
* $ 0 \ leq x \ leq 10 ^ {15} $

Input

The input is given in the following format.


$ a $ $ b $ $ x $


Three integers $ a $, $ b $, $ x $ are given, separated by spaces.

Output

Print the answer on one line.

Examples

Input

3 1 5


Output

7


Input

3 2 5


Output

11


Input

82 69 64


Output

64


Input

316250877917604 316250877917599 681260158257385


Output

62687552

### Response

```cpp
/*  -*- coding: utf-8 -*-
 *
 * 3052.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const long long MOD = 1000000007LL;

/* typedef */

typedef long long ll;

/* global variables */

/* subroutines */

/* main */

int main() {
  ll a, b, x;
  scanf("%lld%lld%lld", &a, &b, &x);

  ll sum = x % MOD;
  if (x >= a) {
    ll k = (x - a) / (a - b) + 1;
    sum = (sum + (k % MOD) * (b % MOD)) % MOD;
  }

  printf("%lld\n", sum);
  return 0;
}


```