Yurik and Woodwork Lesson

Time limit1sMemory limit512 MB

Summary

Count the ways to cut cells from an N by M board so that the top-left and bottom-right cells stay, the rest is connected, and each row and column is one contiguous segment, modulo 998244353.

Level: Hard8 of 10
Topics: Math, Combinatorics
Solved: No attempts yet

Problem

Today Yurik got up early in the morning with great joy because, according to the schedule, the first lesson is woodwork. It is his favorite lesson, since he usually ignores the teacher and plays board games with friends at the back of the classroom. He was disappointed to learn that a test would take place today.

At the start of the lesson, the teacher handed each student a wooden board of size $N \times M$ . Pencil lines divide the board into $N$ rows and $M$ columns, so it consists of $N \cdot M$ unit square cells.

The test is to cut some cells out of the board with a jigsaw so that the remaining part is nice. A board is nice if it satisfies all five conditions:

The upper-left cell of the board is not cut away.
The lower-right cell of the board is not cut away.
The remaining cells form a connected area. Every cell can be reached from every other cell by moving to an adjacent cell left, right, up, or down.
In each row, the remaining cells form one continuous horizontal segment.
In each column, the remaining cells form one continuous vertical segment.

A board that fails at least one of these conditions is ugly. The images below show nice and ugly boards of size $3 \times 4$ . The upper-left and lower-right cells are painted grey.

Yurik never listens to his teacher and loves mathematics, so instead of taking the test he wonders how many different nice boards can be obtained from the original board by cutting away some cells, possibly none. Two boards are different if their sets of cut-away cells differ.

Help Yurik answer this question.

Input

The only line contains two integers $N$ and $M$ , the dimensions of the original board ( $1 \le N, M \le 10^5$ ).

Output

Print a single integer, the number of different nice boards that can be obtained by cutting away some cells from the original board. Since the answer can be very large, print it modulo $998\,244\,353$ .

Hints

The images below show all nice boards that can be cut from a $2 \times 2$ board, and all nice boards that can be cut from a $2 \times 4$ board.

Examples3

Example 1
Input
```
2 2
```
Expected output
```
3
```
Example 2
Input
```
2 4
```
Expected output
```
10
```
Example 3
Input
```
100 100
```
Expected output
```
818380736
```