Description:
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.
Input:
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$).
Output:
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$$$.
Sample Input:
3 2
Sample Output:
2
Sample Input:
4 10
Sample Output:
12
Sample Input:
13 37
Sample Output:
27643508
Sample Input:
1337 42
Sample Output:
211887828
Sample Input:
198756 123456
Sample Output:
159489391
Sample Input:
123456 198756
Sample Output:
460526614
Note:
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]$$$.
