Для массива целых чисел \(a\) обозначим количество элементов в нем за \(|a|\).
Давайте введем две функции:
- \(F(a, k)\) — функция, принимающая массив целых чисел \(a\) и натуральное число \(k\). Результат этой функции — это массив, содержащий \(|a|\) первых элементов массива, который получается заменой каждого элемента \(a\) на \(k\) копий этого элемента.
Например, \(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\).
Массив \(a\) — предок массива \(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\).
А теперь — сама задача.
Вам даны два целых числа \(n\) и \(k\). Ваша цель — построить последовательность массивов \(s_1, s_2, \dots, s_m\), удовлетворяющую следующим условиям:
- каждый массив \(s_i\) содержит ровно \(n\) элементов, и все эти элементы — целые числа от \(1\) до \(k\);
- для каждого массива \(a\), состоящего из ровно \(n\) целых чисел от \(1\) до \(k\), последовательность содержит хотя бы один массив \(s_i\), такой, что \(s_i\) — предок \(a\).
Выведите минимальное количество массивов в такой последовательности.
Выходные данные
Выведите одно целое число — минимальное количество массивов в последовательности, удовлетворяющей условию задачи. Так как ответ может быть очень большим, выведите его по модулю \(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]\).