CF1644F Basis

对于一个整数数组 $a$，我们定义 $|a|$ 为其元素个数。 我们定义两个函数： - $F(a, k)$ 是一个函数，接收一个整数数组 $a$ 和一个正整数 $k$。该函数的结果是：将 $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$ 个元素，结果为 $[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$ 的父数组： - 存在正整数 $k$ 使得 $F(a, k) = b$； - 或存在两个不同的整数 $x$ 和 $y$ 使得 $G(a, x, y) = b$。 如果存在有限序列的数组 $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$ 的父数组，则称数组 $a$ 是数组 $b$ 的祖先。 现在，给定两个整数 $n$ 和 $k$。你的目标是构造一个数组序列 $s_1, s_2, \dots, s_m$，使得： - 每个数组 $s_i$ 恰好包含 $n$ 个元素，且所有元素均为 $1$ 到 $k$ 之间的整数； - 对于每一个由 $n$ 个 $1$ 到 $k$ 之间的整数构成的数组 $a$，序列中至少存在一个数组 $s_i$，使得 $s_i$ 是 $a$ 的祖先。 请输出满足条件的最小数组序列长度。

一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 2 \times 10^5$）。

输出一个整数，表示满足条件的最小数组序列长度。由于答案可能很大，请输出对 $998244353$ 取模后的结果。

我们来分析第一个样例。 第一个样例的一种可行答案是序列 $[[2, 1, 2], [1, 2, 2]]$。所有由 $3$ 个 $1$ 到 $2$ 之间的整数构成的数组，都在该序列中有一个祖先： - 对于数组 $[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]$。 由 ChatGPT 4.1 翻译