You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \ldots, A_N)$ 和一个正整数 $M$。找到序列 $A$ 的非空且不一定连续的子序列的数量，使得子序列中元素的最小公倍数（LCM）为 $M$。计算结果需要对 $998244353$ 取模。即使两个子序列的元素相同，但它们来自序列中的不同位置，这两个子序列也被视为不同的子序列。此外，单个元素的最小公倍数就是它本身。

输入格式

第一行两个正整数 $N, M$

接下来一行 $N$ 个正整数 $A_i$

输出格式

输出一个整数，表示满足条件的子序列的数量，对 $998244353$ 取模。

4 6
2 3 4 6

5

满足条件的子序列有 $(2, 3)$, $(2, 3, 6)$, $(2, 6)$, $(3, 6)$ 和 $(6)$，总共有五个。

5 349
1 1 1 1 349

16

即使某些子序列作为序列是相同的，如果它们来自不同的位置，则它们被视为不同的子序列。

16 720720
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

2688

数据范围与约定

对于 $30\%$ 的数据，满足 $1 \leq N \leq 10, 1 \leq M \leq 100$

对于另外 $10\%$ 的数据，满足 $M = 1$

对于$60\%$ 的数据，满足 $N \leq 100, M \leq 1000$

对于 $100\%$ 的数据：

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 10^{16}$
• $1 \leq A_i \leq 10^{16}$
• 所有输入值均为整数。