#include<iostream>
using namespace std;

//WA
typedef unsigned long long int ll;

int main()
{
    ll a, b, c, sum = 0;
    const ll con = 1000000007;

    cin >> a >> b >> c;

    if( a > c )
    {
        cout << c % con << endl;
        return 0;
    }

    sum += c % con;
    if( ( c - a + 1 ) % ( a - b ) == 0 )
        sum += ( ( c - a + 1 ) / ( a - b ) % con ) * ( b % con );
    else
        sum += ( ( ( c - a + 1 ) / ( a - b ) + 1 ) % con ) * ( b % con );

    cout << sum % con << endl;

    return 0;
}

### 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<iostream>
using namespace std;

//WA
typedef unsigned long long int ll;

int main()
{
    ll a, b, c, sum = 0;
    const ll con = 1000000007;

    cin >> a >> b >> c;

    if( a > c )
    {
        cout << c % con << endl;
        return 0;
    }

    sum += c % con;
    if( ( c - a + 1 ) % ( a - b ) == 0 )
        sum += ( ( c - a + 1 ) / ( a - b ) % con ) * ( b % con );
    else
        sum += ( ( ( c - a + 1 ) / ( a - b ) + 1 ) % con ) * ( b % con );

    cout << sum % con << endl;

    return 0;
}

```