Calling Names

Time limit5sMemory limit1024 MB

Summary

Count the roll-call orders of N by M seats where no two people sitting directly front and back are called consecutively, modulo 998244353.

Level: Medium7 of 10
Topics: Combinatorics, Math, Dynamic programming
Solved: No attempts yet

Problem

Snoopy gets bored in large lectures because roll call takes too long.

One day, bored Snoopy noticed that during roll call, the names of two people who sit adjacent front and back are often called one right after the other, more often than he expected. To check whether this is true, Snoopy decides to calculate it right away.

The lecture hall has seats arranged in a grid of $N$ rows and $M$ columns, and every seat is occupied. During roll call, each person's name is called exactly once. Among all possible orders in which the names can be called, Snoopy wants to count the orders in which the names of two people who are adjacent front and back are never called consecutively.

Input

The first line contains two positive integers $N$ and $M$ , separated by a space. ( $1 \le N \cdot M \le 500\,000$ )

Output

On the first line, print the number of orders that satisfy the condition, modulo 998 244 353.

Examples4

Example 1
Input
```
2 1
```
Expected output
```
0
```
Example 2
Input
```
2 2
```
Expected output
```
8
```
Example 3
Input
```
3 2
```
Expected output
```
152
```
Example 4
Input
```
5 3
```
Expected output
```
278220997
```