AT_KeioPC2025_l Many Max Streak Problems

連勝数に興味のあるけむにく君は以下の問題を作りました。 > **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** を解いてください。

入力は以下の形式で標準入力から与えられる。 > $ N \ M \ P $

答えを出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ N, M \le 30 $ を満たすデータセットに正解した場合 $ 1 $ 点が与えられる。 ### Sample Explanation 1 **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 $ となります。 ### Constraints - $ 1 \le N \le 300 $ - $ 2 \le M \le 300 $ - $ 10^8 \le P \le 10^9 $ - $ P $ は素数 - 入力はすべて整数