Наши герои добрались до космопорта, однако незамеченными им остаться не удалось — почти у самого космопорта они наткнулись на отряд патрульных. Рик с Валлоной чудом смогли сбежать, а сопровождавшему их агенту повезло намного меньше. Но вот они показывают свои недавно полученные паспорта и получают пропуск на корабль до Вотекса, уже ожидающий их на взлетной площадке. Однако теперь их ищут, и сложившиеся обстоятельства требовали отчаянных действий. Неподалеку от их корабля оказался другой, поменьше, на который можно было легко проникнуть. Этот корабль проветривали между полетами, чтобы избавиться от излишков сжатого кислорода, поэтому на корабле не было ни души. Рик и Валлона пробрались внутрь, и затаились в грузовом отсеке. Надо же было из всех кораблей попасть именно на корабль Сэмии Файфской, дочери самого влиятельного человека на всем Сарке!
Тем временем Рик продолжал вспоминать разные моменты из своего прошлого. Ему пришла в голову задача, которую он встретил несколько лет назад. Дано натуральное число $n$, и на доске изначально написано $n times n$. Затем $k$ раз проделывают следующую операцию: вместо каждого вхождения $n times n$ записывается $n$ раз число $n$. Далее между парами этих чисел ставят скобки, объединяя первое со вторым, третье с четвертым, и так далее. Если число $n$ нечетно, то последнее его вхождение в этой записи не заключается в скобки. Затем внутри этих скобок ставится символ "$times$", а между скобками или перед последним числом $n$ — обыкновенное умножение "$dot.op$".
После $k$-й итерации данного процесса, все оставшиеся вхождения "$times$" так же заменяются на "$dot.op$". Рика интересует, сколько символов умножения будет написано на доске после выполнения всех вышеперечисленных операций?
В единственной строке заданы два целых числа $n$ и $k$ $(1 <= n <= 10^9, 0 <= k <= 10^6)$.
Выведите одно число — ответ на задачу Рика по модулю $998244353$.
Выполним первые итерации описанного процесса для $n = 5$. Изначально имеется выражение $5 times 5$.
После первой итерации оно преобразуется в выражение $(5 times 5) dot.op (5 times 5) dot.op 5$.
После второй итерации получится следующее выражение: $((5 times 5) dot.op (5 times 5) dot.op 5) dot.op ((5 times 5) dot.op (5 times 5) dot.op 5) dot.op 5$.
Таким образом, заменяя знаки "$times$" на "$dot.op$" после выполнения $k$ итераций, получаем ответы $1$, $4$ и $10$.
## Входные Данные
В единственной строке заданы два целых числа $n$ и $k$ $(1 <= n <= 10^9, 0 <= k <= 10^6)$.
## Выходные Данные
Выведите одно число — ответ на задачу Рика по модулю $998244353$.
## Примеры
Входные данные5 0
Выходные данные1
Входные данные5 1
Выходные данные4
Входные данные5 2
Выходные данные10
## Примечание
Выполним первые итерации описанного процесса для $n = 5$. Изначально имеется выражение $5 times 5$.После первой итерации оно преобразуется в выражение $(5 times 5) dot.op (5 times 5) dot.op 5$.После второй итерации получится следующее выражение: $((5 times 5) dot.op (5 times 5) dot.op 5) dot.op ((5 times 5) dot.op (5 times 5) dot.op 5) dot.op 5$.Таким образом, заменяя знаки "$times$" на "$dot.op$" после выполнения $k$ итераций, получаем ответы $1$, $4$ и $10$.
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of axis-aligned rectangular obstacles.
Let $ S = (s_x, s_y) $ be the starting point.
Let $ E = (e_x, e_y) $ be the destination point.
For each $ i \in \{1, \dots, N\} $, let $ R_i = [a_i, c_i] \times [b_i, d_i] $ be a closed axis-aligned rectangle (skyscraper), with $ a_i < c_i $, $ b_i < d_i $.
**Constraints**
1. $ 1 \leq N \leq 250000 $
2. $ 0 \leq s_x, s_y, e_x, e_y \leq 10^8 $
3. $ 0 \leq a_i < c_i \leq 10^8 $, $ 0 \leq b_i < d_i \leq 10^8 $ for all $ i $
4. All $ x $-coordinates $ \{s_x, e_x\} \cup \{a_i, c_i \mid i=1,\dots,N\} $ are distinct.
5. All $ y $-coordinates $ \{s_y, e_y\} \cup \{b_i, d_i \mid i=1,\dots,N\} $ are distinct.
6. Rectangles are pairwise non-overlapping.
7. $ S \notin \bigcup_{i=1}^N \text{int}(R_i) $, $ E \notin \bigcup_{i=1}^N \text{int}(R_i) $.
**Objective**
Compute the shortest Manhattan path from $ S $ to $ E $, allowing movement only along horizontal and vertical lines, and permitting passage along the boundaries of rectangles but not through their interiors.
That is, find:
$$
\min_{P \in \mathcal{P}} \left( |p_x^{(1)} - s_x| + |p_y^{(1)} - s_y| + \sum_{j=1}^{m-1} \left( |p_x^{(j+1)} - p_x^{(j)}| + |p_y^{(j+1)} - p_y^{(j)}| \right) + |e_x - p_x^{(m)}| + |e_y - p_y^{(m)}| \right)
$$
where $ \mathcal{P} $ is the set of all polygonal paths $ P = (S = p^{(0)}, p^{(1)}, \dots, p^{(m)}, p^{(m+1)} = E) $ with axis-aligned segments, such that no interior point of any $ R_i $ lies on $ P $, and all $ p^{(j)} $ lie on the union of the boundaries of rectangles and the lines $ x = s_x, x = e_x, y = s_y, y = e_y $.
Equivalently, compute the shortest Manhattan path in the free space $ \mathbb{R}^2 \setminus \bigcup_{i=1}^N \text{int}(R_i) $.