問題文

素数 P が与えられます。 以下の「問題 C'」の答えが 0 になるような N,M,Y を構成してください。

問題 C'

（C 問題との相違点を赤字で示しています。）

2000 \le N \le 2025, 1 \le M \le 10^7 を満たす 正整数 N,M と (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 で割った余りを求めてください。

制約

• 10^9 \le P \le 10^9+1000
• P は素数

入力例 1

3

出力例 1

4 6
2 3 4 1

この入出力例は入出力形式を示すためのものであり、実際には制約を満たさない無効な入力・出力です。