適当自作001

1からnの整数が書かれたカードと、ボタンを押すたびに1からnの整数が等確率で出力する装置があります。
装置のボタンを押しiが出力されたとき、整数iが書かれたカードをまだ持っていなければ
max(1,i-1),i,min(n,i+1)の整数が書かれたカードを入手できる
整数iが書かれたカードを既に持っていれば何も起こりません

カードを一枚も持っていない状態から全ての種類のカードを集め終わるまでにボタンを押す回数の期待値は？
期待値はp/qをmod998244353でどうたらどうたらで求めてください

制約
1<=n<=50

コメント
n<=20ならbitDPをメモ化再帰ですればいい感じに見えます。
n<=50なのでそれは厳しいのですが
状態をまとめたり遷移を考えると
枝刈りを無視してもn以下の分割数程度しか要素は出てこないので普通に再帰が回ります。

でもこれ、n<=50なのでローカル環境でぶん回して埋込みすれば非想定解が通ります。終わり
対策：任意modにするなど

map<vector<int>, mint>dp;
vector<mint>inv;
mint calc(int sz, vector<int> v) {
	if (0 == v.size())return 0;
	if (dp.count(v))return dp[v];
	mint ret(sz);
	rep(i, v.size()) {
		rep(j, v[i]) {
			vector<int>nv = v;
			nv.push_back(j - 1);
			nv.push_back(nv[i] - j - 2);
			nv[i] = 0;
			sort(allR(nv));
			while ((!nv.empty()) && (0 >= nv.back())) nv.pop_back();
			ret += calc(sz, nv);
		}
	}
	int zan = 0;
	rep(i, v.size())zan += v[i];
	ret *= inv[zan];
	dp[v] = ret;
	return ret;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int sz; cin >> sz;
	inv.resize(sz + 1);
	rep2(i, 1, sz + 1)inv[i] = ((mint)i).inv();
	auto get = calc(sz, { sz });
	cout << get.val() << endl;
	return 0;
}