← 返回题目列表

AtCoder · tupc2022_d

D. 泽塔总和

中文机器翻译题面 查看原题

配点 : 300 点

問題文

正整数 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 是质数 答案可以由
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N P

出力

答案 请打印除以 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 除的余数。