题目描述

你有若干袋硬币。每个袋子恰好装有 $k$ 枚硬币。恰好有一个袋子装的全是假币（我们称其为 假袋），而其他所有袋子装的都是真币。所有真币的重量完全相同，所有假币的重量也完全相同。你不知道真币或假币的具体重量。你知道假币严格重于真币，但不知道具体重多少。硬币的重量是正实数。

你有一台天平，最多可以使用 $m$ 次。天平有左右两个托盘。使用时，你可以从任意袋子中取出任意数量的硬币，放在天平两侧，只要左右两侧的硬币总数相等即可。天平会返回一个实数 $s$。如果 $s$ 为零，说明天平两侧重量完全相同。如果 $s$ 为负，说明左侧比右侧重 $|s|$ 克。如果 $s$ 为正，说明右侧比左侧重 $s$ 克。硬币可以重复用于多次称量，并且你可以追踪每枚硬币来自哪个袋子。你必须事先指定所有要进行的称量（即不能根据之前称量的结果调整后续称量）。在使用天平 $m$ 次后，你需要能够确定哪个袋子是假袋。

现在你想知道：给定 $m$ 和 $k$，你总能确定假袋的最大袋子数是多少？这个数字可能很大，因此请输出它对大素数 $998,244,353$ 取模的结果。

输入格式

输入只有一行，包含两个空格分隔的整数 $m$ 和 $k$（$1 \le m,k \le 10^6$），其中 $m$ 是可用的称量次数，$k$ 是每个袋子中的硬币数。

输出格式

输出一个整数，表示在 $m$ 次称量中能确定假袋的最大袋子数，对素数 $998,244,353$ 取模。

2 1

9

2 2

17

提示

样例解释

我们可以用 $2$ 次称量从 $9$ 个袋子中确定假袋（每个袋子有 $1$ 枚硬币）的一种方法如下：

• 第一次称量：将袋子 $1,2,3$ 中的硬币放在左侧，袋子 $7,8,9$ 中的硬币放在右侧。
• 第二次称量：将袋子 $1,4,7$ 中的硬币放在左侧，袋子 $3,6,9$ 中的硬币放在右侧。

我们可以按如下方式确定假袋：

• 第一次称量告诉我们假袋在哪个组中：$(1,2,3)$、$(4,5,6)$ 或 $(7,8,9)$（例如，如果左侧较重，则假袋在 $(1,2,3)$ 中；如果两侧平衡，则假袋在 $(4,5,6)$ 中；否则假袋在 $(7,8,9)$ 中）。
• 第二次称量将告诉我们假袋在哪个组中：$(1,4,7)$、$(2,5,8)$ 或 $(3,6,9)$。由此可以唯一确定假袋。

翻译由 DeepSeek V3.2 完成