P7575 「PMOI-3」公约数

给出 $n,m$ 和一个长度为 $n-1$ 的序列 $x$，保证 $x_i$ 互不相同。 求 $$ \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}]$$ 答案对 $998244353$ 取模。

无

无

【样例解释】 对于第一组样例，只有当 $i_1=1,i_2=2,i_3=2$ 时才满足要求。 【数据范围】 **本题采用捆绑测试。** - Subtask1（10pts）：$n,m\le 5$； - Subtask2（15pts）：$n,m\le500$； - Subtask3（15pts）：$n,m\le 5\times 10^3$； - Subtask4（15pts）：$n,m\le 5\times 10^4$。 - Subtask5（20pts）：$n,m\le 3\times 10^5$。 - Subtask6（25pts）：无特殊限制。 对于 $100\%$ 的数据满足，$n-1\le m$，$1\le n,m\le 10^6$，$1\le x_i\le m$，保证 $x_i$ 互不相同。