/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
正整数 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) の 3 通りです。
入力例 2
3 3 1 2 2
出力例 2
0
条件を満たす A は存在しません。
入力例 3
6 1000000000000000000 380214083 420492929 929717250 666796775 209977152 770361643
出力例 3
325683519
998244353 で割った余りを求めることに注意してください。
Score : 600 points
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.