Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Базис
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива целых чисел $$$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$$$.

Выведите минимальное количество массивов в такой последовательности.

Входные данные

В единственной строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$).

Выходные данные

Выведите одно целое число — минимальное количество массивов в последовательности, удовлетворяющей условию задачи. Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.

Примеры
Входные данные
3 2
Выходные данные
2
Входные данные
4 10
Выходные данные
12
Входные данные
13 37
Выходные данные
27643508
Входные данные
1337 42
Выходные данные
211887828
Входные данные
198756 123456
Выходные данные
159489391
Входные данные
123456 198756
Выходные данные
460526614
Примечание

Давайте проанализируем первый пример.

Один из возможных ответов для первого примера — последовательность $$$[[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]$$$.