你有若干袋硬币。每一袋恰好包含 $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 次称量确定 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)。最终可以唯一确定假袋。

样例

输入 1

2 1

输出 1

9

输入 2

2 2

输出 2

17