题目描述

考虑 $(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$

输出格式

输出答案。

输入输出样例 #1

输入 #1

2 1 1

输出 #1

499122177

输入输出样例 #2

输入 #2

3 1 2

输出 #2

124780545

输入输出样例 #3

输入 #3

4 3 2

输出 #3

260479386

输入输出样例 #4

输入 #4

2022 12 25

输出 #4

741532295

说明/提示

数据范围

• $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 翻译