Basis

题意翻译

有两种对于数组的变换： - $F(a,k)$ 为将数组 $a$ 的每一个数替换成 $k$ 个该数后取前 $|a|$ 个数的数组，例如 $a = [2,2,1,3,5,6,8]$ ，每个数替换成 $2$ 个该数为 $[2,2,2,2,1,1,3,3,5,5,6,6,8,8]$ ，所以 $F(a,2)=[2,2,2,2,1,1,3]$。 - $G(a,x,y)$ 为将数组 $a$ 中每一个 $x$ 替换成 $y$，每一个 $y$ 替换成 $x$，例如$G([1,1,2,3,5],3,1)=[3,3,2,1,5]$。 现要求构造出 $m$ 个数组，其中每个数组都有 $n$ 个数，每个数为不超过 $k$ 的正整数。同时对于所有含 $n$ 个数且每个数为不超过 $k$ 的正整数的数组，你要满足在这 $m$ 个数组中至少存在一个数组在的经过任意多次上述两个函数的变换后能得到它。 你只需要求出所有构造方案中最小的 $m$ 是多少，答案对 $998244353$ 取模。

题目描述

For an array of integers $ a $ , let's define $ |a| $ as the number of elements in it. Let's denote two functions: - $ F(a, k) $ is a function that takes an array of integers $ a $ and a positive integer $ k $ . The result of this function is the array containing $ |a| $ first elements of the array that you get by replacing each element of $ a $ with exactly $ k $ copies of that element.For example, $ F([2, 2, 1, 3, 5, 6, 8], 2) $ is calculated as follows: first, you replace each element of the array with $ 2 $ copies of it, so you obtain $ [2, 2, 2, 2, 1, 1, 3, 3, 5, 5, 6, 6, 8, 8] $ . Then, you take the first $ 7 $ elements of the array you obtained, so the result of the function is $ [2, 2, 2, 2, 1, 1, 3] $ . - $ G(a, x, y) $ is a function that takes an array of integers $ a $ and two different integers $ x $ and $ y $ . The result of this function is the array $ a $ with every element equal to $ x $ replaced by $ y $ , and every element equal to $ y $ replaced by $ x $ .For example, $ G([1, 1, 2, 3, 5], 3, 1) = [3, 3, 2, 1, 5] $ . An array $ a $ is a parent of the array $ b $ if: - either there exists a positive integer $ k $ such that $ F(a, k) = b $ ; - or there exist two different integers $ x $ and $ y $ such that $ G(a, x, y) = b $ . An array $ a $ is an ancestor of the array $ b $ if there exists a finite sequence of arrays $ c_0, c_1, \dots, c_m $ ( $ m \ge 0 $ ) such that $ c_0 $ is $ a $ , $ c_m $ is $ b $ , and for every $ i \in [1, m] $ , $ c_{i-1} $ is a parent of $ c_i $ . And now, the problem itself. You are given two integers $ n $ and $ k $ . Your goal is to construct a sequence of arrays $ s_1, s_2, \dots, s_m $ in such a way that: - every array $ s_i $ contains exactly $ n $ elements, and all elements are integers from $ 1 $ to $ k $ ; - for every array $ a $ consisting of exactly $ n $ integers from $ 1 $ to $ k $ , the sequence contains at least one array $ s_i $ such that $ s_i $ is an ancestor of $ a $ . Print the minimum number of arrays in such sequence.

输入输出格式

输入格式

The only line contains two integers $ n $ and $ k $ ( $ 1 \le n, k \le 2 \cdot 10^5 $ ).

输出格式

Print one integer — the minimum number of elements in a sequence of arrays meeting the constraints. Since the answer can be large, output it modulo $ 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

说明

Let's analyze the first example. One of the possible answers for the first example is the sequence $ [[2, 1, 2], [1, 2, 2]] $ . Every array of size $ 3 $ consisting of elements from $ 1 $ to $ 2 $ has an ancestor in this sequence: - for the array $ [1, 1, 1] $ , the ancestor is $ [1, 2, 2] $ : $ F([1, 2, 2], 13) = [1, 1, 1] $ ; - for the array $ [1, 1, 2] $ , the ancestor is $ [1, 2, 2] $ : $ F([1, 2, 2], 2) = [1, 1, 2] $ ; - for the array $ [1, 2, 1] $ , the ancestor is $ [2, 1, 2] $ : $ G([2, 1, 2], 1, 2) = [1, 2, 1] $ ; - for the array $ [1, 2, 2] $ , the ancestor is $ [1, 2, 2] $ ; - for the array $ [2, 1, 1] $ , the ancestor is $ [1, 2, 2] $ : $ G([1, 2, 2], 1, 2) = [2, 1, 1] $ ; - for the array $ [2, 1, 2] $ , the ancestor is $ [2, 1, 2] $ ; - for the array $ [2, 2, 1] $ , the ancestor is $ [2, 1, 2] $ : $ F([2, 1, 2], 2) = [2, 2, 1] $ ; - for the array $ [2, 2, 2] $ , the ancestor is $ [1, 2, 2] $ : $ G(F([1, 2, 2], 4), 1, 2) = G([1, 1, 1], 1, 2) = [2, 2, 2] $ .