对于整数数组 $$$a$$$,我们将 $$$|a|$$$ 定义为其中的元素数量。
让我们表示两个函数:
- $$$F(a, k)$$$ 是一个函数,它接受整数数组 $$$a$$$ 和正整数 $$$k$$$。此函数的结果是包含 $$$|a|$$$ 数组的第一个元素的数组,通过将 $$$a$$$ 的每个元素替换为该元素的 $$$k$$$ 副本而获得。例如,$$$F([2, 2, 1, 3, 5, 6, 8], 2)$$$ 计算如下:首先,将数组的每个元素替换为 $$$2$$$ 的副本,因此您获得$$$[2,2,2,2,1,1,3,3,5,5,6,6,8,8]$$$。然后,取出获得的数组的前 $$$7$$$ 元素,因此该函数的结果为 $$$[2, 2, 2, 2, 1, 1, 3]$$$。
- $$$G(a, x, y)$$$ 是一个函数,它接受整数数组 $$$a$$$ 和两个不同的整数 $$$x$$$ 和 $$$y$$$。该函数的结果是数组 $$$a$$$,其中等于 $$$x$$$ 的每个元素都替换为 $$$y$$$,等于 $$$y$$$ 的每个元素都替换为 $$$x$$$。例如,$$$G([1, 1, 2, 3, 5], 3, 1) = [3, 3, 2, 1, 5]$$$。
数组 $$$a$$$ 是数组 $$$b$$$ 的父数组,如果:
- 要么存在正整数 $$$k$$$ 使得 $$$F(a, k) = b$$$;
- 或者存在两个不同的整数 $$$x$$$ 和 $$$y$$$ 使得 $$$G(a, x, y) = b$$$。
如果存在数组 $$$c_0, c_1, \dots, c_m$$$ ($$$m \ge 0$$$) 的有限序列,使得 $$$c_0$$$ 是 $$$a$$$,$$$c_m$$$ 是 $$$b$$$,并且对于每个$$$i \in [1, m]$$$, $$$c_{i-1}$$$ 是 $$$c_i$$$ 的父级。
现在,问题本身。
给你两个整数 $$$n$$$ 和 $$$k$$$。您的目标是构造一个数组序列 $$$s_1, s_2, \dots, s_m$$$ ,方式如下:
- 每个数组 $$$s_i$$$ 恰好包含 $$$n$$$ 个元素,并且所有元素都是从 $$$1$$$ 到 $$$k$$$ 的整数;
- 对于每个由 $$$1$$$ 到 $$$k$$$ 之间的 $$$n$$$ 整数组成的数组 $$$a$$$,该序列至少包含一个数组 $$$s_i$$$,使得 $$$s_i$$$ 是 $$$a$$$ 的祖先。
打印该序列中数组的最小数量。
输入
唯一的一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$)。
输出
打印一个整数 — 满足约束的数组序列中元素的最小数量。由于答案可能很大,因此输出它对 $$$998244353$$$ 取模。
示例
输入 #1
3 2
输出 #1
2
输入 #2
4 10
输出 #2
12
输入 #3
13 37
输出 #3
27643508
输入#4
1337 42
输出#4
211887828
输入 #5
198756 123456
输出 #5
159489391
输入 #6
123456 198756
输出 #6
460526614
注意
我们来分析第一个例子。
第一个示例的可能答案之一是序列 $$$[[2, 1, 2], [1, 2, 2]]$$$。每个大小为 $$$3$$$ 的数组由从 $$$1$$$ 到 $$$2$$$ 的元素组成,其祖先序列如下:
- 对于数组 $$$[1, 1, 1]$$$,祖先是 $$$[1, 2, 2]$$$: $$$F([1, 2, 2], 13) = [1, 1, 1]$$$;
- 对于数组 $$$[1, 1, 2]$$$,祖先是 $$$[1, 2, 2]$$$: $$$F([1, 2, 2], 2) = [1, 1, 2]$$$;
- 对于数组 $$$[1, 2, 1]$$$,祖先是 $$$[2, 1, 2]$$$: $$$G([2, 1, 2], 1, 2) = [1, 2, 1]$$$;
- 对于数组$$$[1, 2, 2]$$$,祖先是$$$[1, 2, 2]$$$;
- 对于数组 $$$[2, 1, 1]$$$,祖先是 $$$[1, 2, 2]$$$: $$$G([1, 2, 2], 1, 2) = [2, 1, 1]$$$;
- 对于数组 $$$[2, 1, 2]$$$,祖先是 $$$[2, 1, 2]$$$;
- 对于数组 $$$[2, 2, 1]$$$,祖先是 $$$[2, 1, 2]$$$: $$$F([2, 1, 2], 2) = [2, 2, 1]$$$;
- 对于数组 $$$[2, 2, 2]$$$,祖先是 $$$[1, 2, 2]$$$:$$$G(F([1, 2, 2], 4), 1, 2) = G([1, 1, 1], 1, 2) = [2, 2, 2]$$$。