CF1644F.Basis

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.

对于一个整数数组 $a$，定义 $|a|$ 为其元素个数。

我们定义两个函数：

• $F(a, k)$ 是一个以整数数组 $a$ 和正整数 $k$ 为输入的函数。该函数的结果是一个长度为 $|a|$ 的数组，其元素为：将 $a$ 中每个元素各自替换为恰好 $k$ 个该元素后所得新数组的前 $|a|$ 个元素。

  例如，计算 $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$ 个元素（因为原数组长度 $|a|=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$ 的父数组（parent），当且仅当满足以下任一条件：

• 存在某个正整数 $k$，使得 $F(a, k) = b$；
• 或存在两个互异整数 $x$ 和 $y$，使得 $G(a, x, y) = b$。

称数组 $a$ 是数组 $b$ 的祖先数组（ancestor），当且仅当存在一个有限数组序列 $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$ 之间的整数；
• 对任意一个由恰好 $n$ 个取自 $1$ 到 $k$ 的整数构成的数组 $a$，该序列中至少存在一个数组 $s_i$，使得 $s_i$ 是 $a$ 的祖先数组。

请输出满足上述条件的序列的最小可能数组个数（即最小的 $m$）。

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

唯一一行包含两个整数 $n$ 和 $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$.

输出一个整数——满足约束条件的数组序列中元素的最少个数。由于答案可能很大，请对 $998244353$ 取模后输出。

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

我们来分析第一个例子。

第一个例子的一个可能答案是序列 $[[2, 1, 2], [1, 2, 2]]$。每个由 $1$ 到 $2$ 中的元素构成、长度为 $3$ 的数组，在该序列中均存在一个祖先：

• 对于数组 $[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]$。