Problem Description

Given \( n, m \) and a sequence \( x \) of length \( n-1 \), where \( x_i \) are guaranteed to be distinct.

Calculate
\[ \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}] \]

The answer should be taken modulo \( 998244353 \).

Input Format

The first line contains two integers \( n \) and \( m \).

The next line contains \( n-1 \) integers representing the sequence \( x \).

Output Format

Output a single integer.

Sample Input and Output

Sample Input #1

3 2
1 2

Sample Output #1

1

Sample Input #2

5 20
1 2 4 6

Sample Output #2

312

Sample Input #3

5 20
2 3 1 4

Sample Output #3

592

Sample Input #4

10 1000
1 2 4 8 16 32 64 128 256 

Sample Output #4

207388829

Notes

Sample Explanation

For the first sample, the only combination that satisfies the conditions is when \( i_1 = 1, i_2 = 2, i_3 = 2 \).

Data Range

This problem uses batched testing.

• Subtask1 (10pts): \( n, m \le 5 \);
• Subtask2 (15pts): \( n, m \le 500 \);
• 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): No special constraints.

For 100% of the data, \( n-1 \le m \), \( 1 \le n, m \le 10^6 \), \( 1 \le x_i \le m \), and \( x_i \) are guaranteed to be distinct.

见题面 Input 部分

见题面 Output 部分