102167: [AtCoder]ABC216 H - Random Robots

Problem Statement

There are $K$ robots on a number line. The $i$-th robot $(1 \leq i \leq K)$ is initially at the coordinate $x_i$.

The following procedure is going to take place exactly $N$ times.

• Each robot chooses to move or not with probability $\frac{1}{2}$ each. The robots that move will simultaneously go the distance of $1$ in the positive direction, and the other robots will remain still.

Here, all probabilistic decisions are independent.

Find the probability that no two robots meet, that is, there are never two or more robots at the same coordinate at the same time throughout the procedures, modulo $998244353$ (see Notes).

Notes

It can be proved that the probability in question is always a rational number. Additionally, under the Constraints in this problem, when that value is represented as $\frac{P}{Q}$ using two coprime integers $P$ and $Q$, it can be proved that there uniquely exists an integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find this $R$.

Constraints

• $2 \leq K \leq 10$
• $1 \leq N \leq 1000$
• $0 \leq x_1 \lt x_2 \lt \cdots \lt x_K \leq 1000$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$K$ $N$
$x_1$ $x_2$ $\ldots$ $x_K$

Output

Print the answer.

Sample Input 1

2 2
1 2

Sample Output 1

374341633

The probability in question is $\frac{5}{8}$.

We have $374341633 \times 8 \equiv 5\pmod{998244353}$, so you should print $374341633$.

Sample Input 2

2 2
10 100

Sample Output 2

1

The probability in question may be $1$.

Sample Input 3

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

Sample Output 3

553220346

问题描述

数轴上有 $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$

输出

打印答案。

样例输入 1

2 2
1 2

样例输出 1

374341633

问题中的概率为 $\frac{5}{8}$。

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

样例输入 2

2 2
10 100

样例输出 2

1

问题中的概率可能是 $1$。

样例输入 3

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

样例输出 3

553220346