CODECHEF My Fair Coins

*--------------------------------------------CODECHEF NEW START -----------------------------------------****

                         My Fair Coins

There are coins of 2 different denominations in Crazyland, 1-cent coins and 2-cent coins. As all the coins do, even these coins have two faces, i.e. heads and tails.
Your task is to find out the the number of ways to create a linear arrangement of these coins so that their sum is N cents. The only condition on the linear arrangement is that
the first coin in the arrangement should always face heads. All other coins could either face head or face tail.

Take N = 2 as an example. The possible arrangements are (1H, 1H), (2H), (1H, 1T), where H is heads and T is tails.
Therefore there are 3 possible arrangements that sum up to 2-cents.

Note

While counting make sure that you count heads and tails as different.

Input

First line contains T, the number of cases.

T lines follow, each containing a single number N, the required sum.

Constraints

0 <= T <= 10000

1 <= N <= 1000000000

Output

For each case the output should be a single integer representing the number of such arrangements possible. As this can be very large print it modulo 1000000007.

Sample Input

3
1
2
3

Sample Output

1
3
8

********************************************EDITORIAL************************************************

PROBLEM:

There are infinite coins of two types - of value 1 and of value 2. All coins have two sides - heads and tails. You're to find out number of ways of arranging some coins such that their sum is equal to N (input) and the first coin is heads up.

QUICK EXPLANATION:

Let f(N) denote number of ways of arranging some coins such that their sum is equal to N and the first coin is heads up. Then it can be shown that f(N) = 2 (f(N-1) + f(N-2) ) with f(1) = 1 and f(2) = 3. Using matrix exponentiation, f(N)can be computed in time O(log N).

DETAILED EXPLANATION:

Let f(n, H) denote the number of ways of arranging coins such that their sum is n, and the first coin is heads up. Similarly let f(n, T) denote the number of ways of arranging coins such that their sum is n and first coin is tails up.

Our original problem is to find out f(n, H).

Here are our three claims:


f(n, H) = f(n, T)


f(n, H) = f(n-1, H) + f(n-1, T) + f(n-2, H) + f(n-2, T)


f(n, H) = 2 * ( f(n-1, H) + f(n-2, H) )



Let's see why each of these claims hold:


f(n, H) = f(n, T)
This is true because if we invert every coin of an arrangement with sum of n and first coin heads up, we get an arrangement with sum of n with first coin tails up. It is easy to see that it is infact a bijection. Hence the claim.


f(n, H) = f(n-1, H) + f(n-1, T) + f(n-2, H) + f(n-2, T)
This is the chief step of the problem : Let's look at a particular arrangement with sum of n and first coin heads up. First coin is either of value 1 or of value 2. In first case, sum of remaining coins is n-1 and their first coin could be either heads up or heads down. f(n-1, H) + f(n-1, T) account for such case. In other case, when first coin is of value 2, sum of remaining coins is n-2 and they could either be heads up or tails up. f(n-2, H) + f(n-2, T) account for these. So total : f(n, H) = f(n-1, H) + f(n-1, T) + f(n-2, H) + f(n-2, T) holds.


f(n, H) = 2 * ( f(n-1, H) + f(n-2, H) )
This follows from claims 1 and 2 naturally :)



Now we can drop H from the notation to get f(n) = 2 f(n-1) + 2 f(n-2) with base case of this recurrence as f(1) = 1and f(2) = 3. We can use matrix exponentiaion to solve for this recurrence. For those of you who don't know this very useful technique, I'm providing a short description here itself.

Let's write it in form of matrices:
[ f(n) f(n-1) ] = [ f(n-1) f(n-2) ] * | 2 1 |
                                      | 2 0 |


You can verify that this is nothing but the recurrence we just wrote. Special property of writing it in this form is we [ f(n-1) f(n-2) ] is exactly of the same form as [ f(n) f(n-1) ] and so we can in turn expand it to get:
[ f(n) f(n-1) ] = [ f(n-2) f(n-3) ] * | 2 1 | * | 2 1 |
                                      | 2 0 |   | 2 0 |


We can continue expanding term on right handside till we get :
[ f(n) f(n-1) ] = [ f(2) f(1) ] *   | 2 1 |^(n-2)
                                    | 2 0 |


We can do a matrix exponentiation in time O(log N) using repeated squaring. So we can find out f(N) as well in O(log N) time as well. As we've to report final answer modulo (10^9 + 7), we would do all operations modulo (10^9 + 7)





/***********************************************CODE*********************************************/

#include<iostream>

using namespace std;

#define mod 1000000007

typedef long long int lli;

  void matmult(long long int   a[][2],long long  int  b[][2],long long int  c[][2])//multiply matrix a and b. put result in c

{

    long long int i,j,k;

    for(i=0;i<2;i++)

    {

        for(j=0;j<2;j++)

        {

            c[i][j]=0;

            for(k=0;k<2;k++)

            {

                c[i][j]+=(a[i][k]*b[k][j]);

                c[i][j]=c[i][j]%mod;

            }

        }

    }



}



  void matpow(long long int Z[][2],long long int n,long long int  ans[][2])

//find ( Z^n )% M and return result in ans

{



    long long int temp[2][2];

    //assign ans= the identity matrix initily ans always = identity metrix 

    ans[0][0]=1;

    ans[1][0]=0;

    ans[0][1]=0;

    ans[1][1]=1;

    long long int i,j;

    while(n>0)

    {

        if(n&1)

        {

            matmult(ans,Z,temp);//z*ans

            for(i=0;i<2;i++)

                for(j=0;j<2;j++)

                    ans[i][j]=temp[i][j];

        }

        matmult(Z,Z,temp);// z*z

        for(i=0;i<2;i++)

            for(j=0;j<2;j++)

                Z[i][j]=temp[i][j];// COPYING  RESULT IN Z[][]





        n=n/2;

    }

    return;

     

}

  

   

long long int findFibonacci(long long int n)

{

     

        long long int  fib;

    

    

        long long int Z[2][2]={{2,2},{1,0}},result[2][2];//modify matrix a[][] for other recurrence relations

        matpow(Z,n-2,result);

        fib=(result[0][0]*3+ result[0][1]*1)%mod;    //final multiplication of Z^(n-2) with the initial terms of the series

    // IF U SEE THE RECURRENCE  THAN U WILL FIND THAT [F[N],F[N-1] ]=Z^N-2 [F[2],F[1]]

// SO F(N)= F[2]*RESULT[0][0]+F[1]*RESULT[0][1]

// ALSO F[2]=3, F[1]=1;; 

     // cout<<result[0][0]<<" "<<cout<<result[0][1]<<endl;

        return fib;



}

 int main()

   {

    int t;

     cin>>t;

      while(t--)

       {

        

       

    long long int n,m;

      

    cin>>n;   

    if(n==1 ) cout<<n<<endl;

    else if (n==2) cout<<n+1<<endl;

    else

    {

     long long int ll=findFibonacci(n);

      cout<<ll<<endl;

    }

   

}

   return 0;

   }

*******************************************************END*******************************************