注意第一问不取模！！！
因为a+b=a|b+a&b,a^b=a|b-a&b，所以a+b=a^b+2(a&b)
x^3x==2x可根据异或的性质以转成x^2x==3x，根据上面的推导，得到
x^2x=x+2x-2(x&2x)==3x;
3x-2*(x&2x)==3x;
x&2x==0;
x&(x<<1)==0
也就是说x在二进制下不能有相邻的1
第一问用数位dp瞎搞一下就行
第二问，考虑递推，设f[i]为n==i的答案，已知f[n-1],f[n]，求f[n+1]，考虑在新增的位置上放0，那么剩下n个位置可以随便放，也就是f[n]；在新增的位置上放1，那么n-1位一定要放0，剩下n-1个位置可以随便放，也就是f[n-1]，所以f[n+1]=f[n]+f[n-1]，就是斐波那契数列，用矩阵乘法加速即可
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1e9+7;
long long T,n,b[65],tot,x,ha[65][2];
struct qwe
{
long long a[5][5];
void clr()
{
a[1][1]=a[1][2]=a[2][1]=a[2][2]=0;
}
qwe operator * (const qwe &b) const
{
qwe c;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
{
c.a[i][j]=0;
for(int k=1;k<=2;k++)
c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j])%mod;
}
return c;
}
}aa;
long long dfs(int w,int lm,int la)
{
if(!w)
return 1;
if(!lm&&ha[w][la])
return ha[w][la];
if(lm)
{
if(b[w]==0||la==1)
return dfs(w-1,b[w]==0,0);
else
return dfs(w-1,0,0)+dfs(w-1,1,1);
}
if(la==1)
ha[w][la]=dfs(w-1,0,0);
else
ha[w][la]=dfs(w-1,0,0)+dfs(w-1,0,1);
return ha[w][la];
}
int main()
{
scanf("%lld",&T);
aa.a[1][2]=aa.a[2][1]=aa.a[2][2]=1;
while(T--)
{
memset(b,0,sizeof(b));
memset(ha,0,sizeof(ha));
scanf("%lld",&n);
tot=0;x=n;
while(x)
b[++tot]=x%2,x/=2;
qwe r,a=aa;
r.a[1][1]=r.a[2][2]=1,r.a[1][2]=r.a[2][1]=0;
x=n+1;
while(x)
{
if(x&1)
r=r*a;
a=a*a;
x>>=1;
}
printf("%lld\n%lld\n",dfs(tot,1,0)-1,(r.a[1][1]+r.a[1][2])%mod);
}
return 0;
}