問題文

連勝数に興味のあるけむにく君は以下の問題を作りました。

Max Streak Problem

正整数 N, M と長さ N の数列 W, L が与えられます。

W_i = x であるような i \ (1 \le i \le N) であって「 i \lt j \le N かつ L_j = x であるような j が存在しない」 i の個数を f(x) とします。
このとき \displaystyle \max_{1 \le x \le M} f(x) を求めてください。

ただし、与えられる数列 W, L について 1 \le W_i, L_i \le M および W_i \ne L_i が成立することが保証されます。

しかし、はるるん君はこの問題を簡単すぎると感じたため、次の問題を考えました。

Many Max Streak Problems

長さが N の数列 W, L の組であって Max Streak Problem の入力として考えられるものは、すべてで \big ( M \times (M - 1) \big ) ^ N 通りあります。
それらすべてについての Max Streak Problem の答えの総和を P で割ったあまりを求めてください。

Many Max Streak Problems を解いてください。

制約

• 1 \le N \le 300
  
• 2 \le M \le 300
  
• 10^8 \le P \le 10^9
  
• P は素数
• 入力はすべて整数

部分点

この問題には部分点が設定されている。

• N, M \le 30 を満たすデータセットに正解した場合 1 点が与えられる。

入力例 1

2 2 998244353

出力例 1

6

Max Streak Problem の入力としてありうる (W, L) は以下の 4 通りです。

• ((1, 1),(2, 2)) のとき、答えは 2
• ((1, 2),(2, 1)) のとき、答えは 1
• ((2, 1),(1, 2)) のとき、答えは 1
• ((2, 2),(1, 1)) のとき、答えは 2

となるため、答えは 6 となります。

入力例 2

7 7 202602157

出力例 2

123958978

入力例 3

46 35 924844033

出力例 3

88210081