#include <bits/stdc++.h>
using LL = long long;
const LL MOD = 1e9+7;

using namespace std;


int main(){
    auto calc = [](LL A,LL B,LL C){
        LL ans = C;
        while(C > A){
          //  cout<<C<<endl;
            LL ins = (C-A)/(A-B)+1;
            if(ins == 0)break;
            ans += (B%MOD)*(ins%MOD);
            C = C + B*ins - ins*A;
            ans %= MOD;
        }
        if(C == A)ans += B%MOD;
        return ans%MOD;
    };/*
    for(int a = 0;a < 1000;a++){
        for(int b = 1;b < a;b++){
            for(int c = 0;c < 1000;c++){
                LL ans = c;
                LL w = c;
                while(w >= a){
                    LL q = w/a;
                    ans += q*b;
                    w+=q*b-q*a;
                }

                if(max(ans,0LL) != calc(a,b,c)){
                    cout<<a<<" "<<b<<" "<<c<<" "<<max(ans,0LL)<<" "<<calc(a,b,c)<<endl;
                }

              //  cout<<a<<" "<<b<<" "<<c<<" "<<ans<<endl;
            }
        }
    }
    */

    LL A,B,C;cin >>A >> B >> C;
    cout<<calc(A,B,C)<<endl;
}


### Prompt

Please formulate 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>
using LL = long long;
const LL MOD = 1e9+7;

using namespace std;


int main(){
    auto calc = [](LL A,LL B,LL C){
        LL ans = C;
        while(C > A){
          //  cout<<C<<endl;
            LL ins = (C-A)/(A-B)+1;
            if(ins == 0)break;
            ans += (B%MOD)*(ins%MOD);
            C = C + B*ins - ins*A;
            ans %= MOD;
        }
        if(C == A)ans += B%MOD;
        return ans%MOD;
    };/*
    for(int a = 0;a < 1000;a++){
        for(int b = 1;b < a;b++){
            for(int c = 0;c < 1000;c++){
                LL ans = c;
                LL w = c;
                while(w >= a){
                    LL q = w/a;
                    ans += q*b;
                    w+=q*b-q*a;
                }

                if(max(ans,0LL) != calc(a,b,c)){
                    cout<<a<<" "<<b<<" "<<c<<" "<<max(ans,0LL)<<" "<<calc(a,b,c)<<endl;
                }

              //  cout<<a<<" "<<b<<" "<<c<<" "<<ans<<endl;
            }
        }
    }
    */

    LL A,B,C;cin >>A >> B >> C;
    cout<<calc(A,B,C)<<endl;
}


```