H - 随机机器人

得分：600分

题目描述

一条数轴上有$K$个机器人。第$i$个机器人（$1 \leq i \leq K$）最初处在坐标$x_i$处。

下面的步骤会进行$N$次。

• 每个机器人以概率$\frac{1}{2}$选择移动或不移动。移动的机器人会同时向正方向移动$1$个单位，其他的机器人保持不动。

在这里，所有的概率决定是独立的。

计算机器人不相遇的概率，即在整个过程中从未有两个或更多机器人同时处在同一坐标上的概率，模$998244353$（见注释）。

注释

可以证明所得的概率始终是有理数。另外，在问题的约束下，当该值被表示为分数$\frac{P}{Q}$时，其中$P$和$Q$是两个互质的整数，可以证明唯一存在一个整数$R$，满足$R \times Q \equiv P\pmod{998244353}$和$0 \leq R \lt 998244353$。找出这个$R$。

约束

• $2 \leq K \leq 10$
• $1 \leq N \leq 1000$
• $0 \leq x_1 \lt x_2 \lt \cdots \lt x_K \leq 1000$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$K$ $N$

$x_1$ $x_2$ $\ldots$ $x_K$

输出

打印答案。

2 2
1 2

374341633

所求的概率为 $\frac{5}{8}$。

我们有 $374341633 \times 8 \equiv 5 \pmod{998244353}$，所以应该打印 $374341633$。

2 2
10 100

1

所求的概率可能为 $1$。

10 832
73 160 221 340 447 574 720 742 782 970

553220346