# 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;
}