問題
長さ$ \ N \ $の数列$ \ A = (a_1,a_2,\ldots,a_N) \ $が与えられます。
$A \ $から$ \ 1 \ $つ以上の要素を選んだとき、選んだ全ての要素の積が$ \ K \ $と互いに素となる選び方は何通りあるでしょうか？$ \ 998244353 \ $で割った余りを求めてください。
なお、$2 \ $つの選び方について、選んだ値の集合が同一だとしても添え字の集合が異なる場合は異なる選び方とします。
入力
入力は以下の形式で標準入力から与えられる。
$N \ K$ $a_1 \ a_2 \ \ldots \ a_N$
出力
答えを$ \ 998244353 \ $で割った余りを出力せよ。出力の末尾には改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq K \leq 10^{18}$
- $1 \leq a_i \leq 10^{18} \ (1 \leq i \leq N)$
- 入力は全て整数
入出力例
入力例1
5 2 2 3 4 5 6
出力例1
3
次の$ \ 3 \ $つの選び方が条件を満たします。
- $a_2 $を選んだ場合、積は$ \ 3 \ $となりこれは$ \ K \ $と互いに素です。
- $a_2 \ $と$ \ a_4 \ $を選んだ場合、積は$ \ 3 \times 5 = 15 \ $となりこれは$ \ K \ $と互いに素です。
- $a_4 \ $を選んだ場合、積は$ \ 5 \ $となりこれは$ \ K \ $と互いに素です。
入力例2
3 10 10 100 1000
出力例2
0
条件を満す選び方は存在しません。