A5944 | 「2020-2021 集训队作业」Gem Island 2

宝石岛是位于太平洋中部的一个小岛，曾经它被称为地球上最贫穷但最安宁的地方。但现在它却既不贫穷也不安宁。究竟发生了什么呢？

不久前，一个阳光明媚的早晨，宝石岛上的所有居民都被惊醒了。这个早晨，每个人手里突然握着一颗闪闪发光的宝石。这些宝石在深夜如魔法般出现了。这让大家欢呼雀跃——每个人都忽然变得富有，终于能够买下他们曾经渴望的所有东西，同时他们的岛名也变得更有意义。

第二天，某个人突然被另一个惊喜惊醒：他的一颗宝石神奇地分裂成两颗宝石！在接下来的每个晚上同样的事情都在发生：每晚有恰好一颗宝石分裂成两颗宝石，且每颗宝石有均等的概率在这个晚上分裂。

过了一段时间，宝石岛上的居民拥有了非常多的宝石，其中有些人拥有的宝石数量很多，而有些人很少。为什么有一些居民拥有比其他居民更多的宝石呢？是他们作弊了，还是他们只是幸运，或者另有隐情？

岛上的长者们向你求助，他们希望你确定这个不公平的分配能否纯粹用概率解释。肯定的答案将会大大缓解岛上的紧张氛围。

岛上有 $n$ 个居民，你决定确定 $d$ 个夜晚之后的宝石分配情况。你对拥有前 $r$ 多宝石的人的宝石数量和的期望尤其感兴趣。更加形式化地，设在 $d$ 天之后将 $n$ 个居民的宝石数降序排序得到一个序列 $a_1\geq a_2\geq\cdots\geq a_n$，那么 $a_1+\cdots+a_r$ 的期望是多少？

答案对 $998244353$ 取模。

输入包含一行，共三个整数 $n,d,r(1\leq n,d\leq 1.5\times 10^7,1≤r≤n)$，意义见题目描述。

输出一个整数表示 $d$ 天之后拥有前 $r$ 多的宝石的人的宝石数量和的期望对 $998244353$ 取模后的结果。