AT_abc236_h [ABC236Ex] Distinct Multiples

题目描述

给定正整数 $N,\ M$ 以及正整数序列 $D = (D_1, \dots, D_N)$。

请计算满足以下条件的正整数序列 $A = (A_1, \dots, A_N)$ 的总数，并输出其对 $998244353$ 取模的结果。

• 对于每个 $i$（$1 \leq i \leq N$），有 $1 \leq A_i \leq M$。
• 对于所有 $1 \leq i < j \leq N$，有 $A_i \neq A_j$。
• 对于每个 $i$（$1 \leq i \leq N$），$A_i$ 是 $D_i$ 的倍数。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$ $D_1$ $D_2$ $\ldots$ $D_N$

输出格式

输出满足条件的序列 $A$ 的总数对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

3 7
2 3 4

输出 #1

3

输入输出样例 #2

输入 #2

3 3
1 2 2

输出 #2

0

输入输出样例 #3

输入 #3

6 1000000000000000000
380214083 420492929 929717250 666796775 209977152 770361643

输出 #3

325683519

说明/提示

限制条件

• $2 \leq N \leq 16$
• $1 \leq M \leq 10^{18}$
• $1 \leq D_i \leq M\ \ (1 \leq i \leq N)$
• 输入均为整数。

样例解释 1

满足条件的 $A$ 有 $(2, 3, 4),\ (2, 6, 4),\ (6, 3, 4)$ 共 $3$ 种。

样例解释 2

不存在满足条件的 $A$。

样例解释 3

请注意需要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译