P7575 "PMOI-3" Common Divisors

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$.

The first line contains two integers $n$ and $m$. The next line contains $n-1$ integers, representing $x_i$.

Output one integer in a single line.

[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