algospot - asymtiling

//algospot - asymtiling
 
#include <iostream>
#include <vector>
using namespace std;
 
#define MOD 1000000007
 
int N;
//cache[size] : size 크기만큼의 타일을 채울수 있는 경우의 수
vector<int> cache;
 
void init()
{
    cin >> N;
    cache = vector<int>(N + 1, -1);
}
 
//dp[idx] = dp[idx-1] + dp[idx-2]
//dp[1] = 1, dp[2] = 2
int dp(int idx)
{
    if (idx == 1)
        return 1;
    else if (idx == 2)
        return 2;
    int &ret = cache[idx];
    if (ret != -1)
        return ret;
    ret = dp(idx - 1) + dp(idx - 2);
    ret %= MOD;
    return ret;
}
 
int main()
{
    int C;
    cin >> C;
    for (int tn = 0; tn < C; ++tn)
    {
        init();
        if (N == 2)
            cout << 0 << "\n";
        else if (N % 2)
            cout << (dp(N) - dp(N / 2) + MOD) % MOD << "\n";
        else
            cout << (((dp(N) - dp(N / 2 - 1)+MOD) % MOD) - dp(N / 2) + MOD) % MOD << "\n";
    }
}