1006.Funny Function

Problem Description
Function Fx,ysatisfies:
F1,1=F1,2=1
F1,i=F1,i−1+2∗F1,i−2(i>=3)
Fi,j=∑j+N−1k=jFi−1,k(i>=2,j>=1)
For given integers N and M,calculate Fm,1 modulo 1e9+7.

Input
There is one integer T in the first line.
The next T lines,each line includes two integers N and M .
1<=T<=10000,1<=N,M<263.

Output
For each given N and M,print the answer in a single line.

Sample Input
2
2 2
3 3
Sample Output
2
33

找规律的数学题，规律当时是找出来了，结果不会算。。
规律是:

//AC: 46MS 1680K
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
LL qpow(LL x,LL n){
    LL ret=1;
    for(;n;n>>=1){
    if(n&1)
        ret=ret*x%mod;
    x=x*x%mod;
    }
    return ret;
}
LL inv(LL x)
{
    return qpow(x,mod-2);
}
int T;
LL n,m;
LL ans;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        if(n&1)    ans=(qpow(qpow(2,n)-1,m-1)*2%mod+1)*inv(3)%mod;
        else ans=qpow(qpow(2,n)-1,m-1)*2%mod*inv(3)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}