合并锅子

时间限制：$2$ 秒。内存限制：$512$ MB。

题目描述

有 $n$ 口黑锅按顺序排成一行，第 $i$ 口黑锅的大小为正整数 $a_i$。给定一个整数 $T$，保证初始时每口黑锅的大小都小于 $T$，且所有黑锅的大小之和不小于 $T$。

每次操作从当前所有相邻的黑锅对中等概率选择一对，将它们合并为一口新黑锅。新黑锅的大小为两者大小之和，并占据这两口黑锅原来的位置。其余黑锅的相对顺序不变。

第一次出现大小大于或等于 $T$ 的黑锅时，操作立即停止。给定一口初始黑锅的编号 $s$，求此时新产生的黑锅包含第 $s$ 口初始黑锅的概率。

输入格式

输入文件：merge.in。

第一行包含三个整数 $n,T,s$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出文件：merge.out。

输出一个整数，表示所求概率对 $998244353$ 取模后的值。

具体地，若概率约分后为 $u/v$，输出 $u\cdot v^{-1}\bmod998244353$，其中 $v^{-1}$ 表示 $v$ 在模 $998244353$ 意义下的乘法逆元。可以证明，在给定范围内该逆元一定存在。

样例

输入：

3 5 1
2 2 3

输出：

499122177

样例解释

第一次有两对相邻黑锅可选，概率均为 $1/2$。若先合并前两口，得到大小为 $4$ 的黑锅，还需继续合并，最终新锅包含编号 $1$；若先合并后两口，立即得到大小为 $5$ 的黑锅，操作停止，新锅不包含编号 $1$。所求概率为 $1/2$。

附加样例 $\texttt{merge2.in/.ans}$、$\texttt{merge3.in/.ans}$、$\texttt{merge4.in/.ans}$ 分别满足测试点 $9\sim12$、$15\sim16$、$19\sim20$ 的限制。

数据范围

对于所有测试点，$2\le n\le5000$，$1\le s\le n$，$1\le a_i<T\le10^{12}$，$\sum_i a_i\ge T$。

特殊性质 $A$：$\sum_{i=1}^n a_i=T$。

特殊性质 $B$：对于每个 $1\le i<n$，都有 $a_i+a_{i+1}\ge T$。