Ideone.com

download

copy

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define nl cout<<endl
 
#define pii pair<ll,ll>
#define vi  vector<ll>
#define vii vector<pii>
#define mi  map<ll,ll>
#define all(a)  (a).begin(),(a).end()
 
#define pb push_back
#define make make_pair
#define ff first
#define ss second
#define hell 1000000007
 
#define test4(x,y,z,a) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<"		a is "<<a<<endl;
#define test3(x,y,z) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<endl;
#define test2(x,y) cout<<"x is "<<x<<"		y is "<<y<<endl;
#define test1(x) cout<<"x is "<<x<<endl;
#define N 3
ll add(ll a,ll b)
{
	return (a%hell +b%hell)%hell;
}
ll mult(ll a,ll b)
{
	return (a%hell * b%hell)%hell;
}
ll powerr(ll a,ll b,ll m)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%m;
        b/=2;
        a=(a*a)%m;
    }
    return ans%hell;
}
struct matrix
{
	ll arr[N][N];
	void reset()
	{
		memset(arr,0,sizeof(arr));
	}
	void identity()
	{
		rep(i,0,N)
		arr[i][i]=1;
	}	
	matrix operator +(const matrix &o) const
	{
		matrix res;
		rep(i,0,N)
		{
			rep(j,0,N)
			res.arr[i][j]=add(arr[i][j],o.arr[i][j]);
		}
		return res;
	}
	matrix operator *(const matrix &o) const
	{
		matrix res;
		rep(i,0,N)
		{
			rep(j,0,N)
			{
				res.arr[i][j]=0;
				rep(k,0,N)
				{
					res.arr[i][j]=add(res.arr[i][j],mult(arr[i][k],o.arr[k][j]));
				}
			}
		}
		return res;	
	}
};
ll gcd(ll a,ll b)
{
    if(a==0)
        return b;
    else
        return gcd(b%a,a);
}
matrix power(matrix arr,ll x)
{
	matrix res;
	res.reset();
	res.identity();
	while(x)
	{
		if(x&1)
		res=res*arr;
 
		arr=arr*arr;
		x>>=1;
	}
	return res;
}
ll fib(ll n)
{
	if(n<=2)
	return n;
 
	n-=2;
	matrix a;
	a.reset();
	a.arr[0][0]=1;
	a.arr[0][1]=1;
	a.arr[1][0]=1;
	a.arr[1][1]=0;
 
 
	matrix expo;
	expo.reset();
	expo=power(a,n);	
 
	ll ans=(2*(expo.arr[0][0])%hell)%hell + (expo.arr[0][1])%hell;
	ans%=hell;
	return ans;
}
int main()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	ll t;cin>>t;
	while(t--)
	{
		ll p,q,n;cin>>p>>q>>n;
		n++;
		if(n==1)
		{
			cout<<p<<endl;
			continue;
		}
		if(n==2)
		{
			cout<<q<<endl;
			continue;
		}
		if(n==3)
		{
			cout<<(p+q+(p*q)%hell)%hell<<endl;
			continue;
		}
 
		ll t1=(1+p)%hell;
		ll t2=(1+q)%hell;
 
		ll n1=n-3;ll n2=n-2;
 
		ll val1=fib(n1)%hell;
		ll val2=fib(n2)%hell;
 
		val1=powerr(t1,val1,hell)%hell;
		val2=powerr(t2,val2,hell)%hell;
 
		ll ans=(val1*val2)%hell;
		ans=(ans-1+hell)%hell;
		cout<<ans<<endl;
	}
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgaW50IGxsOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxkOwojZGVmaW5lIHJlcChpLGEsYikgIGZvcihsbCBpPWE7aTxiO2krKykKI2RlZmluZSBubCBjb3V0PDxlbmRsCgojZGVmaW5lIHBpaSBwYWlyPGxsLGxsPgojZGVmaW5lIHZpICB2ZWN0b3I8bGw+CiNkZWZpbmUgdmlpIHZlY3RvcjxwaWk+CiNkZWZpbmUgbWkgIG1hcDxsbCxsbD4KI2RlZmluZSBhbGwoYSkgIChhKS5iZWdpbigpLChhKS5lbmQoKQoKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtYWtlIG1ha2VfcGFpcgojZGVmaW5lIGZmIGZpcnN0CiNkZWZpbmUgc3Mgc2Vjb25kCiNkZWZpbmUgaGVsbCAxMDAwMDAwMDA3CgojZGVmaW5lIHRlc3Q0KHgseSx6LGEpIGNvdXQ8PCJ4IGlzICI8PHg8PCIJCXkgaXMgIjw8eTw8IgkJeiBpcyAiPDx6PDwiCQlhIGlzICI8PGE8PGVuZGw7CiNkZWZpbmUgdGVzdDMoeCx5LHopIGNvdXQ8PCJ4IGlzICI8PHg8PCIJCXkgaXMgIjw8eTw8IgkJeiBpcyAiPDx6PDxlbmRsOwojZGVmaW5lIHRlc3QyKHgseSkgY291dDw8InggaXMgIjw8eDw8IgkJeSBpcyAiPDx5PDxlbmRsOwojZGVmaW5lIHRlc3QxKHgpIGNvdXQ8PCJ4IGlzICI8PHg8PGVuZGw7CiNkZWZpbmUgTiAzCmxsIGFkZChsbCBhLGxsIGIpCnsKCXJldHVybiAoYSVoZWxsICtiJWhlbGwpJWhlbGw7Cn0KbGwgbXVsdChsbCBhLGxsIGIpCnsKCXJldHVybiAoYSVoZWxsICogYiVoZWxsKSVoZWxsOwp9CmxsIHBvd2VycihsbCBhLGxsIGIsbGwgbSkKewogICAgbGwgYW5zPTE7CiAgICB3aGlsZShiKQogICAgewogICAgICAgIGlmKGImMSkKICAgICAgICAgICAgYW5zPShhbnMqYSklbTsKICAgICAgICBiLz0yOwogICAgICAgIGE9KGEqYSklbTsKICAgIH0KICAgIHJldHVybiBhbnMlaGVsbDsKfQpzdHJ1Y3QgbWF0cml4CnsKCWxsIGFycltOXVtOXTsKCXZvaWQgcmVzZXQoKQoJewoJCW1lbXNldChhcnIsMCxzaXplb2YoYXJyKSk7Cgl9Cgl2b2lkIGlkZW50aXR5KCkKCXsKCQlyZXAoaSwwLE4pCgkJYXJyW2ldW2ldPTE7Cgl9CQoJbWF0cml4IG9wZXJhdG9yICsoY29uc3QgbWF0cml4ICZvKSBjb25zdAoJewoJCW1hdHJpeCByZXM7CgkJcmVwKGksMCxOKQoJCXsKCQkJcmVwKGosMCxOKQoJCQlyZXMuYXJyW2ldW2pdPWFkZChhcnJbaV1bal0sby5hcnJbaV1bal0pOwoJCX0KCQlyZXR1cm4gcmVzOwoJfQoJbWF0cml4IG9wZXJhdG9yICooY29uc3QgbWF0cml4ICZvKSBjb25zdAoJewoJCW1hdHJpeCByZXM7CgkJcmVwKGksMCxOKQoJCXsKCQkJcmVwKGosMCxOKQoJCQl7CgkJCQlyZXMuYXJyW2ldW2pdPTA7CgkJCQlyZXAoaywwLE4pCgkJCQl7CgkJCQkJcmVzLmFycltpXVtqXT1hZGQocmVzLmFycltpXVtqXSxtdWx0KGFycltpXVtrXSxvLmFycltrXVtqXSkpOwoJCQkJfQoJCQl9CgkJfQoJCXJldHVybiByZXM7CQoJfQp9OwpsbCBnY2QobGwgYSxsbCBiKQp7CiAgICBpZihhPT0wKQogICAgICAgIHJldHVybiBiOwogICAgZWxzZQogICAgICAgIHJldHVybiBnY2QoYiVhLGEpOwp9Cm1hdHJpeCBwb3dlcihtYXRyaXggYXJyLGxsIHgpCnsKCW1hdHJpeCByZXM7CglyZXMucmVzZXQoKTsKCXJlcy5pZGVudGl0eSgpOwoJd2hpbGUoeCkKCXsKCQlpZih4JjEpCgkJcmVzPXJlcyphcnI7CgoJCWFycj1hcnIqYXJyOwoJCXg+Pj0xOwoJfQoJcmV0dXJuIHJlczsKfQpsbCBmaWIobGwgbikKewoJaWYobjw9MikKCXJldHVybiBuOwoKCW4tPTI7CgltYXRyaXggYTsKCWEucmVzZXQoKTsKCWEuYXJyWzBdWzBdPTE7CglhLmFyclswXVsxXT0xOwoJYS5hcnJbMV1bMF09MTsKCWEuYXJyWzFdWzFdPTA7CgoKCW1hdHJpeCBleHBvOwoJZXhwby5yZXNldCgpOwoJZXhwbz1wb3dlcihhLG4pOwkKCglsbCBhbnM9KDIqKGV4cG8uYXJyWzBdWzBdKSVoZWxsKSVoZWxsICsgKGV4cG8uYXJyWzBdWzFdKSVoZWxsOwoJYW5zJT1oZWxsOwoJcmV0dXJuIGFuczsKfQppbnQgbWFpbigpCnsJCglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCWNpbi50aWUoTlVMTCk7CiAgICAgICAgCglsbCB0O2Npbj4+dDsKCXdoaWxlKHQtLSkKCXsKCQlsbCBwLHEsbjtjaW4+PnA+PnE+Pm47CgkJbisrOwoJCWlmKG49PTEpCgkJewoJCQljb3V0PDxwPDxlbmRsOwoJCQljb250aW51ZTsKCQl9CgkJaWYobj09MikKCQl7CgkJCWNvdXQ8PHE8PGVuZGw7CgkJCWNvbnRpbnVlOwoJCX0KCQlpZihuPT0zKQoJCXsKCQkJY291dDw8KHArcSsocCpxKSVoZWxsKSVoZWxsPDxlbmRsOwoJCQljb250aW51ZTsKCQl9CgoJCWxsIHQxPSgxK3ApJWhlbGw7CgkJbGwgdDI9KDErcSklaGVsbDsKCgkJbGwgbjE9bi0zO2xsIG4yPW4tMjsKCgkJbGwgdmFsMT1maWIobjEpJWhlbGw7CgkJbGwgdmFsMj1maWIobjIpJWhlbGw7CgoJCXZhbDE9cG93ZXJyKHQxLHZhbDEsaGVsbCklaGVsbDsKCQl2YWwyPXBvd2Vycih0Mix2YWwyLGhlbGwpJWhlbGw7CgoJCWxsIGFucz0odmFsMSp2YWwyKSVoZWxsOwoJCWFucz0oYW5zLTEraGVsbCklaGVsbDsKCQljb3V0PDxhbnM8PGVuZGw7Cgl9Cn0=

Runtime error #stdin #stdout 0.13s 4404KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/AX8iWe

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language