思路

看到排列和 LIS，所以想到了楊表。

設楊圖單元格數為 \(n\)，則其每一行的格數構成了 \(n\) 的一種整數劃分。

向一個單元格數為 \(n\)，劃分為 \(\lambda\) 的楊圖 \(Y_{\lambda}\) 中，插入 \(1\sim n\) 的排列，我們有鉤長公式，得到的標準楊表的數量 \(d_{\lambda}\) 為：

此時對應排列的 LIS 長度，為楊表第一行的長度 \(|S_{\lambda}|\)。

對于劃分都為 \(\lambda\) 的楊表，我們有 Robinson-Schensted correspondence 定理，它們中兩兩會唯一對應一種排列。則 \(|S_{\lambda}|\) 對答案的貢獻為：

我們欽定楊圖的形態，則答案為：

由于 \(n \le 28\)，最多也就 \(3718\) 種劃分，所以暴力枚舉 \(\lambda\) 即可。

代碼

inline void dfs(int las,int num){
	if(num==n){
		ll val = mul;
		for(int i=1;i<=cnt;++i){
			for(int j=1;j<=Y[i];++j){
				int num = Y[i]-j+1,t = i+1;;
				while(t<=cnt && Y[t]>=j) ++t,++num;
				(val *= inv[num])%=mod;
			}
		}
		(val *= val*Y[1]%mod)%=mod;
		(ans += val)%=mod;
	}
	for(int i=1;i<=las;++i){
		if(num+i>n) break;
		Y[++cnt] = i;
		dfs(i,num+i);
		--cnt;
	}
}
int main(){
	
	read(n); mul = 1;
	for(ll i=1;i<=n;++i) (mul *= i)%=mod;
	for(int i=1;i<=n;++i){
		Y[++cnt] = i;
		dfs(i,i);
		--cnt;
	}
	(ans *= quick_pow(mul,mod-2))%=mod;
	printf("%lld",ans);

	return 0;
}