HR Permutation Happiness

Problem Description:
Happiness is a value defined upon a permutation, where it is given by the number of values with at least one value higher than itself that is adjacent. Given Q queries, output number of size n permutation with at least k happiness, modulo 1e9 + 7.

Constraints:
1 ≤ Q ≤ 100
1 ≤ N ≤ 3000
1 ≤ K ≤ N

Solution:
dp[i][j]: number size i permutation with j unhappiness
Consider inserting values in increasing order. We can classify the transitions into two kinds:
1. Find an unhappy value, and put the current value adjacent to it. The unhappiness of the permutation is not affected.
2. Otherwise the unhappiness increases by one.

Code:

#include <bits/stdc++.h>

const int MOD = 1e9 + 7;

std::vector<std::vector<int>> Dp(int n) {
  std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1));
  dp[1][1] = 1;
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j <= i; ++j) {
      (dp[i + 1][j] += 1LL * dp[i][j] * 2 * j % MOD) %= MOD;
      (dp[i + 1][j + 1] += 1LL * dp[i][j] * (i + 1 - 2 * j) % MOD) %= MOD;
    }
  }
  return dp;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::vector<std::vector<int>> dp = Dp(3000);
  std::for_each(dp.begin(), dp.end(), [&](std::vector<int> &vec) {
    std::partial_sum(vec.begin(), vec.end(), vec.begin(), [&](int a, int b) { return (a + b) % MOD; });
  });
  int Q;
  std::cin >> Q;
  while (Q--) {
    int N, K;
    std::cin >> N >> K;
    std::cout << dp[N][N - K] << std::endl;
  }
  return 0;
}