#P8557. 炼金术(Alchemy)

炼金术(Alchemy)

题目描述

铃是一个爱玩游戏的女孩子。

她在游戏中想要炼制一种稀有合金 —— 这需要 nn 种金属来合成。

她准备好矿石后建造了 kk 个不同的熔炉,当熔炉启动时,会随机炼出这 nn 种金属中的一些(也可能什么都没有)。

如果把每个熔炉炼出的金属收集起来,有了全部 nn 种金属,就能造出合金了。澪对此很好奇,对铃说:「我考考你,有多少种情况可以炼出合金呢?」这个简单的问题铃很快就会做了,你能求出结果吗?

答案可能很大,请对 998244353998244353 取模(即除以 998244353998244353 的余数)后输出。

输入格式

输入一行两个正整数 n,kn,k

输出格式

输出一行一个整数,表示答案。

2 2
9
4 5
923521
233 123
81633405

提示

【样例一解释】
对于所有成功情况,两个熔炉中的金属如下表:

一号 二号
\varnothing {1,2}\{1,2\}
{1}\{1\} {2}\{2\}
{1,2}\{1,2\}
{2}\{2\} {1}\{1\}
{1,2}\{1,2\}
{1,2}\{1,2\} \varnothing
{1}\{1\}
{2}\{2\}
{1,2}\{1,2\}

一共 99 种,因此答案为 99

【数据范围】
对于 30%30\% 的数据,1n,k101\le n,k \le 10
对于 80%80\% 的数据,1n,k1061\le n,k \le 10^6
对于 100%100\% 的数据,1n,k1091\le n,k \le 10^9