Kaaleppi's puzzle

// NONAME-01

#include <bits/stdc++.h>


using namespace std;


long long p = 1000000007;

int n;



long long dp[1011][2];

long long C[1011][1011];
long long F[1011];
long long p2[1011];

void Fill() {
	int i, j;
	C[0][0] =1;
	for (i = 1; i <= 1000; i++) {
		C[i][0] = 1;
		for (j = 1; j <= i; j++) {
			C[i][j] = ( C[i-1][j-1] + C[i-1][j] ) % p;
		}
	}
	F[0] = F[1] = 1;
	for (i = 2; i <= 1000; i++) {
	  F[i] = (i * F[i-1]) % p;
	}
	p2[0] = 1;
	for (i = 1; i <= 1000; i++)
	  p2[i] = (2 * p2[i-1]) % p;
}


long long FF(int n, int i, int j) {
  return (C[i-1][i-j] * C[n-i][j]) % p; // put i conflicts in j bins;
}



void Load()
{
  cin >> n;
}

void Solve()
{
  long long ans;
  int i, j;
  long long cur;
  
  ans = F[n] % p;
  for (i = 1; i <= n-1; i++) {
	  for (j = 1; j <= i && j+i <= n; j++)
	  {
		cur = p2[j];
		cur = (cur * F[n-i]) % p;
		cur = (cur * FF(n, i, j)) % p;
		if (i % 2 == 0)
		  ans = (ans+cur) % p;
		else ans = (ans-cur+p) % p;
	  }
  }
  
  cout << ans << "\n";
}

int main() {
  Fill();
  memset(dp, -1, sizeof(dp));
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int nt, tt;
  cin >> nt;
  for (tt = 0; tt < nt; tt++) {
  Load();
  Solve();
  }
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED