子序列的 LCM

题目描述

给定长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$ 和正整数 $M$。求满足"子序列中所有元素的最小公倍数(LCM)恰好为 $M$"的非空子序列(不要求连续)的个数,对 $998244353$ 取模。

两个子序列即使作为序列完全相同,只要取自原序列中的位置不同,就视为不同的子序列。此外,只含一个元素的序列的 LCM 就是该元素本身。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

样例

4 6
2 3 4 6

5

$A$ 中元素 LCM 为 $6$ 的子序列有 $(2,3),(2,3,6),(2,6),(3,6),(6)$,共 $5$ 个。

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

数据范围

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