← 返回题目列表

AtCoder · kupc2024_p

P. 披萨销毁

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

配点 : 100 点

問題文

1 有圆形的披萨,圆周长和圆周上的一模一样。 N 将其分成相等的部分,N 点 有 P_1, P_2, \cdots P_N 。

最初,披萨没有任何切口,披萨是按照以下规则制作的。 断开连接 M 次。

  • i (1 \le i \le M) 在切割时,实数 从满足 \theta 除以 0 \lt \theta \lt \pi 的实数均匀分布中随机选择一个点 比萨饼圆周在 P_{A_i} 处的切线是点 逆时针围绕 P_{A_i} 沿着旋转 \theta 的直线切割披萨。

修改所有切割完成后披萨分割的预期数量。 使用 998244353 找到它。

期望值 mod 998244353 的定义 可以证明,在这个问题中找到的期望值始终是一个有理数。 此外,在该问题的约束下,要寻求的期望值可以表示为不可约分数。 当表示为 \frac{x}{y} 时 保证不能被 x 是 998244353 整除。 此时 使其满足 xz \equiv y \pmod {998244353} 小于或等于 0 以上 998244352 的整数 z 是唯一确定的。这个 请回答 z 。

制約

  • 所有输入均为整数
  • 1 \le N \le 998244352
  • 1 \le M \le 3 \times 10^5
  • 1 \le A_i \le N

入力

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

N M
A_1 A_2 \cdots A_M

出力

打印答案。


入力例 1

4 2
1 3

出力例 1

748683268

披萨是 有概率 \frac{3}{4} 的概率为 3 分割、\frac{1}{4} 的概率为 4 由于是除法,所以要找到的期望值是 \frac{13}{4} 。


入力例 2

2 2
1 1

出力例 2

3

配列 A 可以包含多个相同的整数。


入力例 3

9 7
3 1 4 1 5 9 2

出力例 3

49296032