atcoder#ABC236H. [ABC236Ex] Distinct Multiples

[ABC236Ex] Distinct Multiples

配点 : 600600

問題文

正整数 N,MN, M および正整数列 D=(D1,,DN)D = (D_1, \dots, D_N) が与えられます。

以下の条件を満たす正整数列 A=(A1,,AN)A = (A_1, \dots, A_N) の総数を 998244353998244353 で割った余りを求めてください。

  • 1AiM(1iN)1 \leq A_i \leq M \, (1 \leq i \leq N)
  • AiAj(1i<jN)A_i \neq A_j \, (1 \leq i \lt j \leq N)
  • i(1iN)i \, (1 \leq i \leq N) について、AiA_iDiD_i の倍数

制約

  • 2N162 \leq N \leq 16
  • 1M10181 \leq M \leq 10^{18}
  • 1DiM(1iN)1 \leq D_i \leq M \, (1 \leq i \leq N)
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

NN MM

D1D_1 \ldots DND_N

出力

答えを出力せよ。

3 7
2 3 4
3

条件を満たす AA(2,3,4),(2,6,4),(6,3,4)(2, 3, 4), (2, 6, 4), (6, 3, 4)33 通りです。

3 3
1 2 2
0

条件を満たす AA は存在しません。

6 1000000000000000000
380214083 420492929 929717250 666796775 209977152 770361643
325683519

998244353998244353 で割った余りを求めることに注意してください。