Title:

Portal

Title:

Pachuli has a bracelet. There are two kinds of beads that can make up the bracelet. One is metal and the other is wood. When the beads adjacent to the gold beads, they will emit gold.
Now, let's ask how many schemes can make the whole Bracelet look golden.

Analysis:

Let's play with the number of feasible placement schemes in general:

n	1	2	3	4	5
gold	1	2	3	5	8
wood	1	1	2	3	5

It's not hard to see that this is the Fibonacci series.
But because of this ring, we will classify and discuss the first placed bead. We won't repeat it here. Let's play with our hands.
It's worth noting that we all add a new one and then consider the number of schemes that can be increased by the last one. But for the first one with wood attribute, obviously, the last one can't put wood attribute, so we don't need to take it into account when calculating.
Because it's Fibonacci recurrence, and it's a direct violence to seek affirmation of TLETLETLE. So we use matrix multiplication for acceleration.

Code:

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define LL long long 
#define LZX 1000000007
using namespace std;
inline LL read() {
    LL d=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
    return d*f;
}  
struct wxn{
    LL a[2][2];
    wxn operator * (wxn &x)
    {
        wxn sum;
        memset(sum.a,0,sizeof(sum.a));
        for(LL i=0;i<2;i++)
          for(LL j=0;j<2;j++)
            for(LL k=0;k<2;k++)
              sum.a[i][j]=(sum.a[i][j]+a[i][k]%LZX*x.a[k][j]%LZX)%LZX;
        return sum;
    }
}base,ans;
int main()
{
    LL t=read();
    while(t--)
    {
        LL n=read()-1;
        base.a[0][0]=0;base.a[0][1]=1;base.a[1][0]=1;base.a[1][1]=1;
        ans.a[0][0]=2;ans.a[0][1]=1;ans.a[1][0]=0;ans.a[1][1]=0;
        while(n)
        {
            if(n&1) ans=ans*base;
            base=base*base;n>>=1;
        }
        printf("%lld\n",ans.a[0][1]%LZX);
    }
    return 0;
}