GCD Sequence Sum

You are given two integers n and m and a sequence x of length n-1 with distinct elements. You need to count the number of sequences i₁, i₂, …, i_n (with each i_j between 1 and m inclusive) such that for every j from 1 to n-1 the following holds:

$$\gcd(i_j,i_{j+1}) = x_j.$$

Output the answer modulo 998244353.

Note: When n is 1, there is no condition and the answer is simply m.

inputFormat

The first line contains two integers n and m (n ≥ 1, m ≥ 1).

If n > 1, the second line contains n-1 space‐separated integers representing the sequence x (all distinct).

outputFormat

Output a single integer: the total number of sequences satisfying the conditions, taken modulo 998244353.

sample

2 5
2

3