随机机器人

题目描述

数轴上有 $K$ 个机器人。第 $i$ 个机器人（$1 \le i \le K$）初始位于坐标 $x_i$。

接下来将进行恰好 $N$ 次以下操作。

• 对 $K$ 个机器人中的每一个，以概率 $\frac{1}{2}$ 决定其「前进」或「停下」。决定「前进」的机器人会同时向正方向移动距离 $1$，决定「停下」的机器人保持原地不动。

这里，所有的概率决定都是相互独立的。

求出在整个操作过程中，从不发生两个机器人相遇的事件，即从没有两个或更多机器人同时位于同一坐标的概率，对 $998244353$ 取模（见「提示」）。

输入格式

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

$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

数据范围

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

提示

可以证明所求概率一定是有理数。此外，在本问题的约束下，当该值用两个互质的整数 $P$ 和 $Q$ 表示为 $\frac{P}{Q}$ 时，可以证明存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \le R \lt 998244353$。请输出这个 $R$。