# PROBLEM LINK:

*Author:* Rajendra Prajapat

*Tester:* Amitabh Paliwal

*Editorialist:* Rajendra Prajapat

# DIFFICULTY:

EASY

# PREREQUISITES:

simple-DP knowledge

# PROBLEM:

Given a series, where T_{0},T_{1} = 1 and T_{2},T_{3} = 2 else T_{n} = T_{n+2} -T_{n-2} where n >=4. Find Nth term.

# QUICK EXPLANATION:

T_{n} = T_{n+2} -T_{n-2} can be written as T_{n} = T_{n-2} + T_{n-4} then it can be solved easily.

# EXPLANATION:

T_{n} = T_{n+2} -T_{n-2}

T_{n+2} = T_{n} + T_{n-2}

T_{n} = T_{n-2} + T_{n-4}

T_{0} = 1

T_{1} = 1

T_{2} = 2

T_{3}= 2

This problem has two subtasks.

Subtask 1 can be solved easily by brute-forcing but subtask 2 can not be, because (number of test cases)*N is very long, which requires more time, but the time limit is only 0.5 seconds. So instead of calculating each term again and again, first we calculate all the values up to 10 ^{5} and store in an array, then for each test-case just print the value from the array.

# SOLUTIONS:

## Setter's Solution

```
#include<iostream>
using namespace std;
int f[100005];
void setup()
{
for(int i=0;i<100000;i++)
{
if(i<=1)
{
f[i] = 1;
}
else if(i>1 and i<=3)
{
f[i] = 2;
}
else
{
f[i]= (f[i-2]%1000000007 + f[i-4]%1000000007)%1000000007;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
setup();
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
cout<<f[n]<<endl;
}
}
```