题目描述

数直線上に $K$ 個のロボットが置かれています。$i\ \,\ (1\ \leq\ i\ \leq\ K)$ 番目のロボットははじめ、座標 $x_i$ に存在します。

これから以下の操作をちょうど $N$ 回行います。

• $K$ 個のロボットそれぞれについて、「進む」か「止まる」かを確率 $\frac{1}{2}$ で決める。「進む」と決めたロボットたちは同時に正の方向に $1$ 進み、「止まる」と決めたロボットたちはその場から動かない。

ただし、すべての確率的な決定は独立であるとします。

一連の操作の中で、複数のロボットが出会う、すなわち $2$ 個以上のロボットが同時に同じ座標に存在する、という事象が一度も起こらない確率を$\mod\ 998244353$ で求めてください（注記参照）。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

有 $K$ 个机器人在数轴上, 位置分别是 $x_1,x_2,\dots,x_K$ , $x$ 均为整数.

接下来 $n$ 秒, 每秒每个机器人有 $\dfrac{1}{2}$ 的概率不动, $\dfrac{1}{2}$ 的概率往坐标轴正方向移动一个单位距离, 机器人的移动同时进行.

求机器人互相不碰撞的概率, 对 $998244353$ 取模.

2 2
1 2

374341633

2 2
10 100

1

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

553220346

提示

注記

求める確率は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $2$ つの整数 $P$, $Q$ を用いて $\frac{P}{Q}$ と表したとき、$R\ \times\ Q\ \equiv\ P\pmod{998244353}$ かつ $0\ \leq\ R\ \lt\ 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $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 $
• 入力は全て整数

Sample Explanation 1

求める確率は $\frac{5}{8}$ です。 $374341633\ \times\ 8\ \equiv\ 5\pmod{998244353}$ ですので、$374341633$ を出力します。

Sample Explanation 2

求める確率が $1$ であることもあります。