For an array of integers $$$a$$$, let's define $$$|a|$$$ as the number of elements in it.
Let's denote two functions:
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]$$$.
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:
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:
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$$$.
3 2
2
4 10
12
13 37
27643508
1337 42
211887828
198756 123456
159489391
123456 198756
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:
Name |
---|