炼金术（Alchemy）

Luogu

IDLGP8557

Time1000ms

Memory128MB

DifficultyP3

数学洛谷原创组合数学容斥原理

铃是一个爱玩游戏的女孩子。她在游戏中想要炼制一种稀有合金 —— 这需要 $n$ 种金属来合成。她准备好矿石后建造了 $k$ 个不同的熔炉，当熔炉启动时，会随机炼出这 $n$ 种金属中的一些（也可能什么都没有）。如果把每个熔炉炼出的金属收集起来，有了全部 $n$ 种金属，就能造出合金了。澪对此很好奇，对铃说：「我考考你，有多少种情况可以炼出合金呢？」这个简单的问题铃很快就会做了，你能求出结果吗？答案可能很大，请对 $998244353$ 取模（即除以 $998244353$ 的余数）后输出。 ## Input 输入一行两个正整数 $n,k$。 ## Output 输出一行一个整数，表示答案。 [samples] ## Note 【样例一解释】对于所有成功情况，两个熔炉中的金属如下表： | 一号 | 二号 | | :----------: | :----------: | | $\varnothing$ | $\{1,2\}$ | | $\{1\}$ | $\{2\}$ | | $\{1\}$ | $\{1,2\}$ | | $\{2\}$ | $\{1\}$ | | $\{2\}$ | $\{1,2\}$ | | $\{1,2\}$ | $\varnothing$ | | $\{1,2\}$ | $\{1\}$ | | $\{1,2\}$ | $\{2\}$ | | $\{1,2\}$ | $\{1,2\}$ | 一共 $9$ 种，因此答案为 $9$。【数据范围】对于 $30\%$ 的数据，$1\le n,k \le 10$；对于 $80\%$ 的数据，$1\le n,k \le 10^6$；对于 $100\%$ 的数据，$1\le n,k \le 10^9$。

Samples

Input #1

2 2

Output #1

Input #2

4 5

Output #2

Input #3

233 123

Output #3

81633405

API Response (JSON)

{
  "problem": {
    "name": "炼金术（Alchemy）",
    "description": {
      "content": "铃是一个爱玩游戏的女孩子。 她在游戏中想要炼制一种稀有合金 —— 这需要 $n$ 种金属来合成。 她准备好矿石后建造了 $k$ 个不同的熔炉，当熔炉启动时，会随机炼出这 $n$ 种金属中的一些（也可能什么都没有）。 如果把每个熔炉炼出的金属收集起来，有了全部 $n$ 种金属，就能造出合金了。澪对此很好奇，对铃说：「我考考你，有多少种情况可以炼出合金呢？」这个简单的问题铃很快就会做了，你能求出",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8557"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "铃是一个爱玩游戏的女孩子。\n\n她在游戏中想要炼制一种稀有合金 —— 这需要 $n$ 种金属来合成。\n\n她准备好矿石后建造了 $k$ 个不同的熔炉，当熔炉启动时，会随机炼出这 $n$ 种金属中的一些（也可能什么都没有）。\n\n如果把每个熔炉炼出的金属收集起来，有了全部 $n$ 种金属，就能造出合金了。澪对此很好奇，对铃说：「我考考你，有多少种情况可以炼出合金呢？」这个简单的问题铃很快就会做了，你能求出...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments