Fisher

問題文

数直線のうち座標が $0$ 以上 $L$ 以下の部分を取り出した線分を考えます。
線分上には魚捕りマシンが $N$ 台設置されており、$i$ 台目のマシンの座標は $A_i$ です。
あなたは線分上の点を $M$ 個選び、選んだ各点にマシンを設置することができます。この操作の後、マシンは合計 $N+M$ 台存在します。

マシンを設置した後、ある座標に魚が $1$ 匹現れます。魚の座標は $0$ 以上 $L$ 以下の実数から一様ランダムに選ばれます。
魚を捕まえる コスト を次のように定義します。

• 魚の座標を $x$ とし、魚に最も近いマシンの座標を $y$ とする。このときコストは $|x-y|$ である。

$M$ 台のマシンを設置する座標を適切に選択したとき、コストの期待値は最小でいくつになりますか？ $\bmod \, 998244353$ で答えてください。

（補足）$\bmod \, 998244353$ で答えるとは？

この問題の制約下では、求める期待値は互いに素な正整数 $P,Q$ を用いて $\frac{P}{Q}$ と表すことができ、さらにこの $P,Q$ に対して $R \times Q \equiv P \pmod{998244353}$ かつ $0 \le R < 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を答えてください。

制約

• $1 \le N \le 10^4$
• $1 \le M \le 4 \times 10^8$
• $N+1 \le L \le 9 \times 10^8$
• $1 \le A_1 < A_2 < \dots < A_N \le L-1$
• 入力される値はすべて整数

入力

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

出力

答えを $1$ 行に出力してください。最後に改行を出力してください。

サンプル

サンプル1

2 1 7
1 6

409993217

座標 $\frac{7}{2}$ にマシンを設置したときコストの期待値が最小となり、その値は $\frac{33}{56}$ です。
整数でない座標にもマシンを設置できることに注意してください。

サンプル2

3 2 4
1 2 3

457528662