Background

In 2077, the time traveler Lanuxhem invented a cipher that converts graphics into numbers in order to contact Silver187 in 2021.

Problem Description

lhm currently has a square with side length $1$. Now he will perform $k$ splits. In each split, he needs to further split the rectangle located at the bottom-right corner of the figure into $n \times n$ rectangles. After all splits are completed, the total number of rectangles is the decrypted answer. lhm needs your help to solve this problem.

Note: Since the description is hard to visualize, please refer to the sample explanation to better understand the task.

Input Format

The input consists of one line.
One line contains two integers $n, k$, with meanings as described in the statement.

Output Format

The output consists of one line.
Output one integer, representing the final answer.
Since the answer may be very large, output it modulo $998244353$.

2 2

7

5 3

73

Hint

Sample Explanation

For Sample #1, perform $2$ splits. Each time, split the bottom-right rectangle into $2 \times 2$ rectangles.

In the first split, since there is only one rectangle, the bottom-right rectangle is exactly this rectangle. Before and after the split are as follows:

becomes

Next, perform the second split and split the bottom-right rectangle. The result is as shown below:

This figure contains $7$ rectangles, so the answer is $7$.

Constraints

For $10\%$ of the testdata, $k = 1$.
For another $20\%$ of the testdata, $1 \leq n, k \leq 10$.
For $100\%$ of the testdata, $1 \leq n, k \leq 10^9$.

$2022.7.10$: A new set of $\text{Hack}$ testdata has been added.

Translated by ChatGPT 5