Score : 1800 points
We have an N \times M grid. The square at the i-th row and j-th column will be denoted as (i,j). Particularly, the top-left square will be denoted as (1,1), and the bottom-right square will be denoted as (N,M). Takahashi painted some of the squares (possibly zero) black, and painted the other squares white.
We will define an integer sequence A of length N, and two integer sequences B and C of length M each, as follows:
How many triples (A,B,C) can occur? Find the count modulo 998244353.
In this problem, the length of your source code must be at most 20000 B. Note that we will invalidate submissions that exceed the maximum length.
Input is given from Standard Input in the following format:
N M
Print the number of triples (A,B,C), modulo 998244353.
2 3
64
Since N=2, given B_i and C_i, we can uniquely determine the arrangement of black squares in each column. For each i, there are four possible pairs (B_i,C_i): (1,1), (1,2), (2,2) and (3,0). Thus, the answer is 4^M=64.
4 3
2588
17 13
229876268
5000 100
57613837