# 2. 题解

$ans = \sum _ {i = 1} ^ {n} f[i][E] \times (n – i + 1) \times [C _ n ^ i \times (n – i)!] ^ 2$

$n – i + 1$表示可以把相似区间插入到 $n – i$个元素形成的 $n – i + 1$个间隔中。

$h[i][j] = \sum _ {k = 0} ^ {i – 1} h[i – 1][j – k]$

#include <bits/stdc++.h>

#define NS (505)
#define ES (124755)
#define MOD (1000000007)

using namespace std;

inline int pls(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b;}
inline int mns(int a, int b) {return a - b < 0 ? a - b + MOD : a - b;}

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int ToT, n, E, f[NS][ES], g[NS], sum[ES], C[NS][NS], P[NS];

void Init()
{
f[1][0] = 1;
for (int i = 2; i <= 500; i += 1)
{
g[i] = (i * (i - 1)) >> 1;
sum[0] = f[i - 1][0];
for (int j = 1; j <= g[i]; j += 1)
sum[j] = pls(sum[j - 1], f[i - 1][j]);
for (int j = 0; j <= g[i]; j += 1)
if (j < i) f[i][j] = sum[j];
else f[i][j] = mns(sum[j], sum[j - i]);
}
for (int i = 1; i <= 500; i += 1)
for (int j = 1; j <= g[i]; j += 1)
f[i][j] = pls(f[i][j], f[i][j - 1]);
for (int i = 0; i <= 500; i += 1) C[i][0] = C[i][i] = 1;
for (int i = 2; i <= 500; i += 1)
for (int j = 1; j < i; j += 1)
C[i][j] = pls(C[i - 1][j], C[i - 1][j - 1]);
P[0] = 1;
for (int i = 1; i <= 500; i += 1)
P[i] = 1ll * P[i - 1] * i % MOD;
}

int main(int argc, char const* argv[])
{
IN(ToT), Init();
while (ToT--)
{
IN(n), IN(E); int ans = 0;
for (int l = 1; l <= n; l += 1)
{
ans = pls(ans,
1ll * (n - l + 1)
* C[n][l] % MOD * P[n - l] % MOD
* C[n][l] % MOD * P[n - l] % MOD
* f[l][min(E, g[l])] % MOD);
}
printf("%d\n", ans);
}
return 0;
}