文件详细信息

下载本文件

本文件的大小为 1201 字节。

#include<cstdio>
#include<cstring>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
typedef long long ll;
const ll P=1000000007;
struct Matrix{
	ll v[2][2];
	Matrix(){
		v[0][0]=v[0][1]=v[1][0]=v[1][1]=0;
	}
}I,trans;
Matrix operator*(Matrix A,Matrix B){
	Matrix C;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			C.v[i][j]=(A.v[i][0]*B.v[0][j]+A.v[i][1]*B.v[1][j])%P;
	return C;
}
Matrix qpow(Matrix A,ll k){
	Matrix ans=I;
	while(k){
		if(k&1)ans=ans*A;
		A=A*A;
		k>>=1;
	}
	return ans;
}
ll n;
ll f[64][2];
ll dfs(int digit,int last,bool lim){
	if(digit==-1)return 1;
	if(!lim&&f[digit][last])return f[digit][last];
	int d=lim?((n>>digit)&1):1;
	ll ans=0;
	for(int i=0;i<=d;i++)
		if(!last||!i)
			ans+=dfs(digit-1,i,lim&&i==d);
	if(!lim)f[digit][last]=ans;
	return ans;
}
void solve(){
	read(n);
	printf("%lld\n",dfs(63,1,1)-1);
	Matrix ans;
	ans.v[0][0]=ans.v[0][1]=1;
	ans=ans*qpow(trans,n-1);
	printf("%lld\n",(ans.v[0][0]+ans.v[0][1])%P);
}
int main(){
	I.v[0][0]=I.v[1][1]=1;
	trans.v[0][0]=trans.v[0][1]=trans.v[1][0]=1;
	int t;
	read(t);
	while(t--)solve();
	return 0;
}