AT_tupc2022_d Zeta Sum

正整数 $ 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 $ で割った余りを求めてください。

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

答えを $ P $ で割った余りを出力せよ。

### Sample Explanation 1 与式は $ (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 $ です。 ### Sample Explanation 3 素数 $ 520232023 $ で割った余りを求めてください。 ### Constraints - $ 1 \leq N \leq 2\times10^5 $ - $ 10^8 \leq P \leq 10^9 $ - $ P $ は素数 - 入力はすべて整数