给你三个数组:
- 数组 $$$a$$$,最初由 $$$n$$$ 个组成;
- 数组 $$$b$$$,最初由 $$$m$$$ 零组成;
- 数组 $$$c$$$,由从 $$$1$$$ 到 $$$50$$$ 的 $$$m$$$ 整数组成。
我们对这些数组执行以下过程。该过程由 $$$m$$$ 个阶段组成。在第 $$$i$$$ 阶段,会发生以下情况:
- 首先, 对于数组 $$$a$$$ 的每个元素,三个操作之一是 独立 选择 :乘以某个素数,除以某个素数(不能除以不能整除该元素的数),或者保持不变。您不必为 $$$a$$$ 的每个元素选择相同的操作或素数;
- 那么您可以跳过此步骤或选择任何 $$$k$$$ 使得 $$$a_k = c_i$$$,并分配 $$$b_i = k$$$。
调用从 $$$0$$$ 到 $$$n$$$ 的 $$$m$$$ 数字数组 可实现 如果此过程的结果可以作为数组 $$$b$$$ 获得。
您的任务是计算可实现的数组的数量。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^4$$$)。
第二行包含 $$$m$$$ 整数 $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_i \le 50$$$)。
输出
打印一个整数 — 可实现的数组数量,以 $$$998244353$$$ 为模。
示例
输入复制
4 34 2 3
输出复制
21
输入复制
2 41 2 3 4
输出复制
51
输入复制
1 247 34
输出复制
3