Problem Description

Find the number of ways to paint all squares of an $H \times W$ grid in white or black such that it is possible to place some number of $1 \times 2$ tiles (some of which may be rotated if necessary) to satisfy the following conditions, modulo $ 998244353 $.

• Tiles must not extend beyond the grid, and no two different tiles can overlap.
• Each tile completely covers exactly 2 squares.
• All white-painted squares are covered by exactly one tile.
• All black-painted squares are not covered by any tile.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $

Output Format

Output the number of valid paint patterns that satisfy the conditions.

Sample Input and Output

Sample Input #1

2 2

Sample Output #1

6

Sample Input #2

3 4

Sample Output #2

550

Sample Input #3

5 100

Sample Output #3

655553721

Notes/Hints

Constraints

• $1 \leq H \leq 5$
• $1 \leq W \leq 10^9$
• All inputs are integers.

Sample Explanation 1

There is 1 way to paint all squares white, 1 way to paint all squares black, and 4 ways to paint 2 adjacent squares black and the remaining 2 squares white, totaling 6 ways that satisfy the conditions.

见题面 Input 部分

见题面 Output 部分