#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  ll a,b,x;
  cin>>a>>b>>x;

  if(x<a){
    cout<<x%MOD<<endl;
    return 0;
  }
  
  ll ans=(x-a)/(a-b)+1;
  ans%=MOD;
  b%=MOD;
  x%=MOD;
  ans=ans*b%MOD+x;
  ans=(ans+MOD)%MOD;
  cout<<ans<<endl;

  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
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  ll a,b,x;
  cin>>a>>b>>x;

  if(x<a){
    cout<<x%MOD<<endl;
    return 0;
  }
  
  ll ans=(x-a)/(a-b)+1;
  ans%=MOD;
  b%=MOD;
  x%=MOD;
  ans=ans*b%MOD+x;
  ans=(ans+MOD)%MOD;
  cout<<ans<<endl;

  return 0;
}


```