← 返回题目列表

Codeforces · 2199/I

I. 奇怪的过程

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

给你三个数组:

  • 数组 $$$a$$$,最初由 $$$n$$$ 个组成;
  • 数组 $$$b$$$,最初由 $$$m$$$ 零组成;
  • 数组 $$$c$$$,由从 $$$1$$$ 到 $$$50$$$ 的 $$$m$$$ 整数组成。

我们对这些数组执行以下过程。该过程由 $$$m$$$ 个阶段组成。在第 $$$i$$$ 阶段,会发生以下情况:

  1. 首先, 对于数组 $$$a$$$ 的每个元素,三个操作之一是 独立 选择 :乘以某个素数,除以某个素数(不能除以不能整除该元素的数),或者保持不变。您不必为 $$$a$$$ 的每个元素选择相同的操作或素数;
  2. 那么您可以跳过此步骤或选择任何 $$$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 3
4 2 3

输出
复制

21

输入
复制

2 4
1 2 3 4

输出
复制

51

输入
复制

1 2
47 34

输出
复制

3