102367: [AtCoder]ABC236 Ex - Distinct Multiples

Problem Statement

Given are positive integers $N$, $M$, and a sequence of positive integers $D = (D_1, \dots, D_N)$.

Find the number of sequences of positive integers $A = (A_1, \dots, A_N)$ that satisfy the following conditions, modulo $998244353$.

• $1 \leq A_i \leq M \, (1 \leq i \leq N)$
• $A_i \neq A_j \, (1 \leq i \lt j \leq N)$
• For each $i \, (1 \leq i \leq N)$, $A_i$ is a multiple of $D_i$.

Constraints

• $2 \leq N \leq 16$
• $1 \leq M \leq 10^{18}$
• $1 \leq D_i \leq M \, (1 \leq i \leq N)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3 7
2 3 4

Sample Output 1

3

The three sequences $A$ that satisfy the conditions are $(2, 3, 4), (2, 6, 4), (6, 3, 4)$.

Sample Input 2

3 3
1 2 2

Sample Output 2

0

No sequence $A$ satisfies the conditions.

Sample Input 3

6 1000000000000000000
380214083 420492929 929717250 666796775 209977152 770361643

Sample Output 3

325683519

Be sure to find the count modulo $998244353$.

问题描述

给定正整数$N$、$M$和一个正整数序列$D = (D_1, \dots, D_N)$。

找出满足以下条件的正整数序列$A = (A_1, \dots, A_N)$的数量，取模$998244353$。

• $1 \leq A_i \leq M \, (1 \leq i \leq N)$
• $A_i \neq A_j \, (1 \leq i \lt j \leq N)$
• 对于每个$i \, (1 \leq i \leq N)$，$A_i$是$D_i$的倍数。

限制条件

• $2 \leq N \leq 16$
• $1 \leq M \leq 10^{18}$
• $1 \leq D_i \leq M \, (1 \leq i \leq N)$
• 输入中的所有值都是整数。

输入

从标准输入以以下格式获取输入：

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

输出

打印答案。

样例输入 1

3 7
2 3 4

样例输出 1

3

满足条件的三个序列$A$是$(2, 3, 4), (2, 6, 4), (6, 3, 4)$。

样例输入 2

3 3
1 2 2

样例输出 2

0

没有序列$A$满足条件。

样例输入 3

6 1000000000000000000
380214083 420492929 929717250 666796775 209977152 770361643

样例输出 3

325683519

确保找到取模$998244353$后的计数。