← 返回题目列表

AtCoder · abc216_h

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

输出

打印答案。


示例输入 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