Kaaleppi's puzzle

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MN = 1111;
const int MOD = 1e9+7;
int ans[MN];
ll dp[3][MN][2]; //e, v

int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    dp[1][0][0] = 1;
    ans[1] = 1;
    for(int i = 2; i <= 1111; ++i) {
        for(int j = 0; j < i; ++j) {
            dp[2][j+1][1] += 2*dp[1][j][0];
            dp[2][j+1][1] %= MOD;

            if(j > 0) {
                dp[2][j-1][0] += dp[1][j][0]*j;
                dp[2][j-1][0] %= MOD;
            }
            int q = i-2-j;
            dp[2][j][0] += q*dp[1][j][0];
            dp[2][j][0] %= MOD;
            if(j > 0) {
                dp[2][j][1] += dp[1][j][1];
                dp[2][j][1] %= MOD;


                int w = i-1-j;
                dp[2][j][0] += dp[1][j][1]*w;
                dp[2][j][0] %= MOD;

                dp[2][j+1][1] += dp[1][j][1];
                dp[2][j+1][1] %= MOD;

                dp[2][j-1][0] += dp[1][j][1] * (j-1);
                dp[2][j-1][0] %= MOD;
            }
        }
        for(int j = 0; j < MN; ++j) {
            for(int k = 0; k < 2; ++k) {
                dp[1][j][k] = dp[2][j][k];
                dp[2][j][k] = 0;
            }
        }
        ans[i] = dp[1][0][0];
    }
    int tt;
    cin>>tt;
    for(int i = 0; i < tt; ++i) {
        int q;
        cin>>q;
        cout<<ans[q]<<'\n';
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED