#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
LL a,b,x;
LL MOD=1e9+7;
int main(){
	cin>>a>>b>>x;
	if(x<a){
		cout<<x%MOD<<endl;
	}else{
		x-=a;
		LL ans=0;
		LL now=x/(a-b);
		ans+=(now%MOD)*(a%MOD);
		ans%=MOD;
		//cout<<ans<<endl;
		x=x%(a-b);
		x+=a;
		//cout<<x<<endl;
		while(x>=a){
			x-=a;
			x+=b;
			ans+=a;
		}
		ans+=x;
		ans%=MOD;
		cout<<ans<<endl;
	}
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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 namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
LL a,b,x;
LL MOD=1e9+7;
int main(){
	cin>>a>>b>>x;
	if(x<a){
		cout<<x%MOD<<endl;
	}else{
		x-=a;
		LL ans=0;
		LL now=x/(a-b);
		ans+=(now%MOD)*(a%MOD);
		ans%=MOD;
		//cout<<ans<<endl;
		x=x%(a-b);
		x+=a;
		//cout<<x<<endl;
		while(x>=a){
			x-=a;
			x+=b;
			ans+=a;
		}
		ans+=x;
		ans%=MOD;
		cout<<ans<<endl;
	}
}

```