AT_agc060_c.[AGC060C] Large Heap

考虑 $(1,2,\cdots,2^N-1)$ 的一个排列 $P=(P_1,P_2,\cdots,P_{2^N-1})$。当 $P$ 满足以下所有条件时，称其为堆式排列：

• $P_i < P_{2i}$（$1 \leq i \leq 2^{N-1}-1$）
• $P_i < P_{2i+1}$（$1 \leq i \leq 2^{N-1}-1$）

给定整数 $A,B$，令 $U=2^A,\ V=2^{B+1}-1$。

从所有堆式排列中等概率随机选取一个，求 $P_U < P_V$ 的概率对 $998244353$ 取模的结果。

概率 $\bmod{998244353}$ 的定义：可以证明，在本题的约束下，所求概率一定是有理数。设其最简分数为 $\frac{P}{Q}$，且 $Q \not\equiv 0 \pmod{998244353}$。因此，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$。请输出这个 $R$。

输入为一行，包含三个整数：

$N\ A\ B$

输出答案。

数据范围

• $2 \leq N \leq 5000$
• $1 \leq A,B \leq N-1$
• 输入的所有数均为整数

样例解释 1

堆式排列有 $P=(1,2,3),(1,3,2)$ 共 $2$ 种。$P_2 < P_3$ 的概率为 $1/2$。

由 ChatGPT 4.1 翻译