#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
  int a,b,n,s=0,mod=1000000007;
  cin>>a>>b>>n;
  int l=0,r=1e15+9;
  while(r-l>1){
    int mid=(l+r)/2;
    if(mid&&(a-b)>=1e18/mid){
      r=mid;
      continue;
    }
    int c=n-mid*(a-b);
    if( c+a-b>=a && c>=0 )l=mid;
    else r=mid;
  }
  cout<< (((n-(l%mod)*(a-b))%mod)+((l%mod)*(a%mod)))%mod <<endl;
}

### Prompt

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

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 <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
  int a,b,n,s=0,mod=1000000007;
  cin>>a>>b>>n;
  int l=0,r=1e15+9;
  while(r-l>1){
    int mid=(l+r)/2;
    if(mid&&(a-b)>=1e18/mid){
      r=mid;
      continue;
    }
    int c=n-mid*(a-b);
    if( c+a-b>=a && c>=0 )l=mid;
    else r=mid;
  }
  cout<< (((n-(l%mod)*(a-b))%mod)+((l%mod)*(a%mod)))%mod <<endl;
}

```