一条路径上有 \(n\) 个位置，有三种元素：\(slime\)，\(npc\)，\(player\)。
\(slime\) 初始会向右移动，\(npc\) 初始会向左移动，所有元素移动速度是相同的：\(1\) 单位距离每 \(1\) 单位时间。
元素的移动遇到边界会改变初始移动方向，并继续移动。
我们称 \(player\) 与 \(npc\) 为人类，\(npc\) 带有初始为 \(0\) 的能力值。
你作为 \(player\) 与 \(npc\) 有相同的移动规则，由于带有主角光环，你若出生在位置 \(i\) 初始会有 \(s_i\) 的能力值。
若有某两元素相遇，他们会开始战斗，战斗不改变移动方向，战斗总是遵循以下两种规则。
1、人类与 \(slime\) 相遇：人类总是胜利，胜利后人类能力值 \(+1\)。
2、人类与人类相遇：能力值大的获胜，若能力值相同，则 \(player\) 获胜，能力值不发生改变。
可以证明，这两条规则覆盖了所有情况。
失败的一方将被立刻移除游戏，胜利的一方将仍继续行进。
由于你是主角，你的左侧总是以 \(100\%\) 的概率刷新 \(slime\)，你的右侧总是分别以 \(50\%\) 的概率刷新 \(npc\) 或者 \(slime\)。
对于 \(1,n\) 两个特殊位置有特殊的刷新规则：\(1\) 号位置总是 \(slime\)，\(n\) 号位置总是 \(npc\)。
你需要求出来你以相同概率随机出生在 \([2,n-1]\) 的某一位置，经过 \(\infty\) 单位时间后，仍存活的概率。
你需要注意，游戏的进程总是 \(player\) 先刷新，然后以一定概率刷新 \(slime\) 和 \(npc\)，然后开始游戏。
可以证明概率总是一个有理数 \(x\over y\)，你只需要输出这个数对 \(998244353\) 取模的结果。
保证 \(s_1=s_n=0\)。
对于所有测试点满足 \(3\leq n\leq 5\times 10^5,0\leq s_i\leq 10^9\)。
一道二项式反演题
我们假设现在在考虑第 \(i\) 位，令 \(B = s_i + i - 1\) ，我们让 \(f(n)\) 表示钦定 \(n\) 个 \(slime\) 长度 \(=B + 1\) ，之后跟一个 \(npc\) 时的方案数(这里如果 \(> B+1\) 的连续段怎么办？一会再说)，我们可以知道 \(g(0) = \sum_{i>0} (-1)^{i} \binom{i}{0} f(i) = \sum_{i>0} (-1)^i f(i)\)
我们考虑怎么求 \(f(k)\) ，我们用组合数，我们先确定 \(k\) 个连续段，然后考虑往这 \(k+1\) 个位置里插入剩下的 \(n - i - 1 - k \times (B + 2)\) 个 \(slime\) (其中 \(-1\) 的原因是我们钦定的是 \(slime\) )，这里直接用插板法：把这些史莱姆插到 \(k+1\) 个空里的方案数
一些细节：由于 \(n\) 号节点始终是 \(npc\) ，我们要讨论在钦定不满足条件的连续段时是否钦定了 \(n\) 这一个 \(npc\)
复杂度分析：有人觉得这是 \(O(n^2)\) 的，但我们发现玩家在 \(i\) 位置时能力值至少为 \(i-1\) ，因此复杂度为调和级数，最终复杂度 \(O(n \log n)\)