C. 洋葱圈 - EOJ Monthly 2021.10 Sponsored by TuSimple

仪表盘所有提交榜单题解

单点时限: 3.0 sec

内存限制: 512 MB

Cuber QQ 最近迷上了洋葱圈。

Cuber QQ 现在有 $n$ 个不同的洋葱和 $m$ 个不同的盘子。每次 Cuber QQ 可以选择一些洋葱串成一个洋葱圈放在某个盘子上。但是，有强迫症的 Cuber QQ 规定第 $i$ ( $1 \leq i \leq n$ ) 个盘子上面只能放长度为 $a_{i}$ 的倍数的洋葱圈。Cuber QQ 需要保证每个洋葱都在其中一个盘子上，一盘子上可以放任意多个洋葱圈，也可以为空。

Cuber QQ 想知道有多少种不同的方案数。

如果两个洋葱圈包含了不同的洋葱，或者包含相同的洋葱但是无法通过旋转使得两个洋葱圈完全一致，则认为两个洋葱圈是不同的。

如果某个盘子在两个方案中放置的洋葱圈不同，则认为两个方案是不同的，同个盘子上的洋葱圈是无序的。

输入格式

输入数据第一行两个整数 $n, m$ ( $1 \leq n, m \leq 2 \cdot 10^{5}$ )。

接下的 $m$ 行，每行一个整数， $a_{i}$ ( $1 \leq a_{i} \leq n$ ) ，表示第 $i$ 个盘子上只能放长度为 $a_{i}$ 的倍数的洋葱圈。

输出格式

输出包含一个整数，表示答案。由于答案可能很大，所以输出模 $998244353$ 的结果。

样例

Input

1 1
1

Output

Input

Output

提示

盘子上的洋葱圈可以旋转，不能翻转。

以下两个洋葱圈是不同的
1 1
/ \ / \
2 - 3 3 - 2

以下两个洋葱圈是相同的
3 1
/ \ / \
2 - 1 3 - 2

NaN

A. Gold B. Secret C. 洋葱圈 D. 赌怪 E. 异或树 F. oh my cuber

比赛状态发生变化，点 OK 刷新。

OK

EOJ Monthly 2021.10 Sponsored by TuSimple

输入格式

输出格式

样例

提示

题目列表

服务

开源

关于我们