Kaaleppi's puzzle

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

const ll M=1e9+7;
ll f[1010];
ll g[1010];
ll a[1010],b[1010];
const ll i2=5e8+4;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	a[2]=2;
	b[2]=0;
	g[2]=2;
	for (int i=3;i<=1000;i++) {
		a[i]=(b[i-1]*i2)%M;
		b[i]=(2*a[i-1]+2*b[i-1])%M;
		g[i]=(a[i]+b[i])%M;
	}
//	for (int i=2;i<=6;i++) cout<<g[i]<<endl;
//	cout<<"--"<<endl;
	f[1]=1;
	f[2]=0;
	f[3]=0;
	for (ll i=4;i<=1000;i++) {
		f[i]=((i-2)*f[i-1])%M;
		for (ll k=2;k<i;k++) {
			ll hlp=(g[k]*(i-k)-2)%M;
			hlp*=f[i-k];
			hlp%=M;
			f[i]+=hlp;
			f[i]%=M;
		}
	}
//	for (int i=1;i<=6;i++) cout<<f[i]<<endl;
	int t;
	cin>>t;
	for (int i=0;i<t;i++) {
		int n;
		cin>>n;
		cout<<f[n]<<"\n";
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED