Problem Description

Given $n$, $m$, and a sequence $x$ of length $n-1$, it is guaranteed that all $x_i$ are pairwise distinct.

Compute

$$\sum_{i_1=1}^m\sum_{i_2=1}^m\cdots\sum_{i_n=1}^m[\gcd(i_1,i_2)=x_1][\gcd(i_2,i_3)=x_2]\cdots[\gcd(i_{n-1},i_n)=x_{n-1}]$$

Output the answer modulo $998244353$.

Input Format

The first line contains two integers $n$ and $m$.

The next line contains $n-1$ integers, representing $x_i$.

Output Format

Output one integer in a single line.

3 2
1 2

1

5 20
1 2 4 6

312

5 20
2 3 1 4

592

10 1000
1 2 4 8 16 32 64 128 256 

207388829

Hint

[Sample Explanation]

For the first sample, the condition is satisfied only when $i_1=1$, $i_2=2$, and $i_3=2$.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (10 pts): $n, m \le 5$.
• Subtask 2 (15 pts): $n, m \le 500$.
• Subtask 3 (15 pts): $n, m \le 5\times 10^3$.
• Subtask 4 (15 pts): $n, m \le 5\times 10^4$.
• Subtask 5 (20 pts): $n, m \le 3\times 10^5$.
• Subtask 6 (25 pts): no special constraints.

For $100\%$ of the testdata, $n-1 \le m$, $1 \le n, m \le 10^6$, $1 \le x_i \le m$, and all $x_i$ are pairwise distinct.

Translated by ChatGPT 5