Саша очень любит комбинаторные задачи, а также он является главным фанатом задачи «Хорошие раскраски», которая появилась на региональном этапе ВсОШ по информатике несколько лет назад. Более того, Саша очень любит играть со спичками. Поэтому мальчик решил придумать свою задачу о хороших раскрасках и порадовать вас своим творением.
Саша выложил в ряд на столе $$$n$$$ квадратов, состоящих из спичек. На рисунке ниже приведен пример получившейся фигуры для $$$n = 3$$$. Можно заметить, что фигура, состоящая из $$$n$$$ квадратов, содержит в себе $$$3n + 1$$$ спичек.
Назовем две спички соседними, если они касаются в углу некоторого квадрата. Например, на рисунке ниже спички, окрашенные синим цветом, являются попарно соседними.
У Саши в распоряжении есть краски $$$k$$$ различных цветов, и, разумеется, он хочет окрасить каждую спичку выложенной фигуры в некоторый цвет. Саша считает раскраску спичек хорошей, если никакие две соседние спички не окрашены в один цвет.
Будучи любителем комбинаторных задач, Саша задумался, сколько существует различных хороших раскрасок спичек. Помогите Саше решить данную тривиальную задачу. Так как ответ может быть достаточно большим, вам необходимо вычислить остаток от деления количества хороших раскрасок на число $$$998\,244\,353$$$.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — количество квадратов из спичек, которые выложил на столе Саша.
Вторая строка содержит одно целое число $$$k$$$ ($$$3 \le k \lt 998\,244\,353$$$) — количество различных цветов, которые может использовать Саша.
Обратите внимание, что входные данные в этой задаче могут превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Выведите одно целое число — остаток от деления количества различных хороших раскрасок на число $$$998\,244\,353$$$.
15
260
35
223380
1000000000000000000900000000
591253139
Баллы за подзадачи 1, 2, 4 – 8 начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Баллы за каждый тест в подзадаче 3 начисляются независимо, если все тесты необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | 0 | Тесты из условия | полная | |
| 1 | 5 | $$$n \le 4$$$, $$$k = 3$$$ | первая ошибка | |
| 2 | 10 | $$$n \le 20$$$, $$$k = 3$$$ | 1 | первая ошибка |
| 3 | 10 | $$$n \le 30$$$, $$$k = 3$$$ | 1, 2 | полная |
| 4 | 5 | $$$n = 1$$$ | первая ошибка | |
| 5 | 15 | $$$n \le 100$$$, $$$k \le 10$$$ | 1, 2, 3 | первая ошибка |
| 6 | 20 | $$$n \le 10^6$$$ | 1 – 5 | первая ошибка |
| 7 | 15 | $$$n \le 10^9$$$ | 1 – 6 | первая ошибка |
| 8 | 20 | нет | 1 – 7 | первая ошибка |
