問題文

正整数 n に対し、\zeta_n:=\cos{\left(\dfrac{2\pi}{n}\right)}+\sqrt{-1}\sin{\left(\dfrac{2\pi}{n}\right)} とします。

正整数 N が与えられるので、

\[ \sum_{a=1}^{N}\sum_{b=1}^{N}\sum_{i=0}^{a-1}\sum_{j=0}^{b-1}(\zeta_a^i+\zeta_b^j)^N \]

を求めてください。
但し、この値は整数になる事が示されます。
答えは大きくなる場合があるので、入力として与えられる素数 P で割った余りを求めてください。

制約

• 1 \leq N \leq 2\times10^5
• 10^8 \leq P \leq 10^9
• P は素数
• 入力はすべて整数

入力例 1

2 998244353

出力例 1

20

与式は (1+1)^2+(1+1)^2+(1-1)^2+(1+1)^2+(-1+1)^2+(1+1)^2+(1-1)^2+(-1+1)^2+(-1-1)^2=20 です。

入力例 2

5 998244353

出力例 2

490

入力例 3

200000 520232023

出力例 3

340864157

素数 520232023 で割った余りを求めてください。