题目描述

给出 $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$ 取模。

输入格式

第一行两个数 $n,m$。

接下来一行 $n-1$ 个整数，表示 $x_i$。

输出格式

一行一个整数。

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

提示

【样例解释】

对于第一组样例，只有当 $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$ 互不相同。