Output is correct till 42.Can anyone point out the mistake. I guess its in the modulo operation


#1

int help(vector&dp,int i,int n)
{
if(i==n-1)
return 3;

if(i>n)
return 1;

if(dp[i]!=-1)
return dp[i];

int i2;int k1=0,k2=0;
k2=((help(dp,i+2,n)%1000000007)*3)%1000000007;

//cout<<k2<<" ";
for(i2=4;i+i2-1<=n;i2+=2)
{
    //cout<<"e";
 k1=((k1%1000000007)+((help(dp,i+i2,n)*2))%1000000007)%1000000007;
 
}




dp[i]=(k1+k2)%1000000007;

return dp[i];

}

int Solution::solve(int n) {
if(n%2!=0)
return 0;

vector<int>dp(n+1,-1);
int g= help(dp,1,n);
//for(int i=0;i<=n;i++)
//cout<<dp[i]<<" ";
return g;

}


#2

int Solution::solve(int N) {
vector A(N+1), B(N+1);
int MOD = 1000000007;
A[0] = 1, A[1] = 0, B[0] = 0, B[1] = 1;
for(int i = 2; i <= N; i++) {
A[i] = A[i-2] + (2*B[i-1])%MOD, A[i] %= MOD;
B[i] = A[i-1] + B[i-2], B[i] %= MOD;
}
return A[N]%MOD;
}