#P18031. Penguin Flicker

Penguin Flicker

Penguin Flicker

一条直线上的格子编号为 1,2,…,L1,2,\ldots,L,位置 00 和 L+1L+1 是洞。初始有 NN 只企鹅,分别位于 P1<P2<⋯<PNP_1<P_2<\cdots<P_N,每个格子最多一只企鹅。

反复进行以下随机操作,直到所有企鹅都掉进洞中:

  1. 在当前剩余企鹅中等概率选一只。
  2. 以相同概率选择向左或向右。
  3. 这只企鹅沿选定方向滑行,直到停在该方向另一只企鹅的相邻格子上,或者滑入洞中。滑入洞中的企鹅立即消失。

相邻企鹅可能使一次操作的移动距离为 00。移动距离按格子编号之差计算,滑入洞的最后一步也计入距离。

求所有企鹅在整个过程中移动距离之和的期望,答案对 998244353998244353 取模。若期望写为最简分数 a/ba/b,输出 a b−1 mod 998244353a\,b^{-1}\bmod998244353;题目保证所需逆元存在。

输入格式

第一行一个整数 TT。每组测试第一行两个整数 N,LN,L,第二行 NN 个整数 P1,…,PNP_1,\ldots,P_N。

输出格式

每组测试输出一行,表示期望值对 998244353998244353 取模的结果。

数据范围

1≤T≤1001\le T\le100,1≤N≤50001\le N\le5000,N≤L≤109N\le L\le10^9,1≤P1<⋯<PN≤L1\le P_1<\cdots<P_N\le L。没有额外的 ∑N\sum N 限制。所有输入均为整数。

样例说明

第一组只有一只企鹅。它从位置 22 向左移动距离为 22,向右移动距离为 77,期望为 9/29/2。

样例 1

输入:

3
1 8
2
4 7638
7 66 333 888
5 21
2 4 9 15 17

输出:

499122181
308996191
485077673