E: 全域木の数え上げ関連の問題を出してもいいですか[吃瓜.jpg]
X: やめて
E: ああ、主に今日、特別な行列の行列式を求めるものを思いついたので
X: 一般的な難易度の数式変形問題でいいよ
$n$ 個のノードを持つすべての根付き木について、それぞれの高さの総和を求めてください。答えは $p$ を法として出力してください。
高さとは、根ノードから到達可能な最長の単純パスの長さのことです。
2 つの根付き木が等しいとは、根ノードの子の数が等しく、かつ左から右へ順に各部分木が対応して等しいことを指します。
入力
2 つの整数 $n, p$ が与えられます。
出力
$n$ 個のノードを持つすべての根付き木の高さの総和を $p$ で割った余りを出力してください。
入出力例
入力 1
4 998244353
出力 1
10
注記
例 1 について：
- 高さ $1$ の木は $1$ 種類：根に直接 $3$ つの子を持つ。
- 高さ $2$ の木は $3$ 種類：
- $1$ つの子を持ち、その子がさらに $2$ つの子を持つもの。
- $2$ つの子を持ち、そのうち一方が葉であるもの。これは $2$ 通りの構成がある（子の順序が区別されるため、最初の子が葉である場合と、2 番目の子が葉である場合に分けられる）。
- 高さ $3$ の木は $1$ 種類：一本の鎖状の木。
入力 2
10 998244353
出力 2
19838
入力 3
514 998244353
出力 3
867876856
サブタスク
- $20\%$ のデータについて、$n \le 50$。
- $40\%$ のデータについて、$n \le 400$。
- $60\%$ のデータについて、$n \le 1000, p = 998244353$。
- $80\%$ のデータについて、$n \le 2000$。
- $100\%$ のデータについて、$1 \le n \le 10^5, 9 \times 10^8 \le p \le 1.01 \times 10^9$、$p$ は素数。