[R37G]烹饪大赛 - 代码源竞赛平台

时空限制

1S/512M

题目描述

兔子 Tom 参加了烹饪大赛，大赛要求每个人使用给定食材中的其中一些做出一道美食，大赛的食材有 $n$ 种，每一种都有一个风味值，用 $a_1,a_2,\cdots,a_n$ 表示。

一道美食的美味程度是根据其食材的种类数和食材搭配的和谐度决定，种类越多或和谐度越高，美食就越美味。大赛的评委有一个品鉴值 $x$，一个由风味值分别为 $b_1,b_2,\cdots,b_m$ 的 $m$ 种食材制作的美食的美味程度为：

$$x^m \times \gcd(b_1,b_2,\cdots,b_m)$$

因为 Tom 对烹饪一无所知，他会随机选择任意数量的食材（至少一种）出来进行烹饪，为了知道他预计的成绩是多少，他需要你输出所有 $2^n-1$ 种情况的美食美味程度之和，由于答案可能很大，请输出对 $998244353$ 取模的结果。

输入格式

第一行包含两个整数 $n,x$，表示食材种数和品鉴值。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每种食材的风味值。

输出格式

输出一行一个整数，表示所有情况下美食的美味程度之和，对 $998244353$ 取模。

样例

样例输入 1

4 1
2 3 4 6

样例输出 1

32

样例输入 2

5 2
2 6 18 25 30

样例输出 2

562

样例输入 3

7 4
12 35 14 5 27 6 15

样例输出 3

80456

数据范围

子任务编号	分数	$n \le$	$a_i \le$	$x<$
$1$	$10$	$18$	$10^6$	$998244353$
$2$	$20$	$300$
$3$	$20$	$2\times 10^5$	$10^6$	$2$
$4$	$50$			$998244353$

对于 $100\%$ 的数据：$1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^6$，$1 \le x < 998244353$。