AT_jsc2025_final_c Prefix Bounding Box, Mod, Minimize

正整数 $ N,M $ と素数 $ P $ と $ (1,2,\dots ,N) $ の順列 $ Y=(Y_1,Y_2,\dots ,Y_N) $ が与えられます。 $ (1,2,\dots ,N) $ の順列 $ X=(X_1,X_2,\dots ,X_N) $ に対して、 $ f(X) $ を以下のように定義します。 - $ 2 $ 以上 $ N $ 以下の整数 $ k $ について以下の値を $ B_k $ としたときの $ \max(B_2,B_3,\dots ,B_N) $ - 座標が $ (X_1,Y_1), (X_2,Y_2), \dots ,(X_k,Y_k) $ であるような $ 2 $ 次元平面上の $ k $ 個の点の集合 $ S $ に対するバウンディングボックスの面積を $ M $ で割った余り $ f(X) $ が最小となるような $ X $ の個数を $ P $ で割った余りを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。 バウンディングボックスとは $ S $ に対するバウンディングボックスとは、 $ S $ に含まれる全ての点を内部または周上に含んでかつ $ x $ 軸に平行な辺を持つような長方形のうち、面積が最小であるものを指します。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ P $ $ Y_1 $ $ Y_2 $ $ \ldots $ $ Y_N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについて、 $ f(X) $ が最小となるような $ X $ の個数を $ P $ で割った余りを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、例えば $ X=(3,1,4,2) $ のとき $ (B_2,B_3,B_4)=(2,0,3) $ であり $ f(X)=3 $ です。 $ f(X) $ の最小値は $ 3 $ であり、 $ f(X)=3 $ となるような $ X $ は $ 12 $ 個存在します。 $ 2 $ つ目のテストケースについて、全ての $ X $ について $ f(X)=0 $ であり、答えは $ 13! $ を $ P=10007 $ で割った余りとなります。 ### Constraints - $ 1 \le T \le 100 $ - $ 2 \le N \le 3000 $ - $ 1 \le M \le 10^7 $ - $ 10^4 \le P \le 10^9 $ - $ P $ は素数 - $ Y $ は $ (1,2, \dots ,N) $ の順列 - 全てのテストケースにおける $ N $ の総和は $ 3000 $ 以下 - 入力される値は全て整数