問題文

正整数 $N,K$ と長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられる。

$1,2,\ldots,N$ の順列 $P=(P_1,P_2,\ldots,P_N)$ に対して、整数 $B(P)$ を

$B(P)=\mathop{\mathrm{lcm}}\limits_{1\le i\le N-K+1}\gcd(A_{P_i},A_{P_{i+1}},\ldots,A_{P_{i+K-1}})$

と定める。

$1,2,\ldots,N$ のすべての順列 $P$ に対する $B(P)$ の最大公約数を $998244353$ で割った余りを求めよ。

制約

• 入力はすべて整数である。
• $2\le N\le 2\times 10^5$
• $1\le K\le N$
• $1\le A_i\le 10^6$ $(1 \le i \le N)$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$

出力

答えを出力せよ。

サンプル

4 2
2 4 6 9

2

5 5
12 18 30 42 66

6