Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

fft

math

number theory

*2900

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Basis

time limit per test

6 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputFor 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$$$.

Examples

Input

3 2

Output

2

Input

4 10

Output

12

Input

13 37

Output

27643508

Input

1337 42

Output

211887828

Input

198756 123456

Output

159489391

Input

123456 198756

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]$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/27/2024 19:17:44 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|