E. Card Game
combinatorics; dp; fft; greedy; math
In the most popular card game in Berland, a deck of \(n \times m\) cards is used. Each card has two parameters: suit and rank. Suits in the game are numbered from \(1\) to \(n\), and ranks are numbered from \(1\) to \(m\). There is exactly one card in the deck for each combination of suit and rank.A card with suit \(a\) and rank \(b\) can beat a card with suit \(c\) and rank \(d\) in one of two cases: \(a = 1\), \(c \ne 1\) (a card of suit \(1\) can beat a card of any other suit); \(a = c\), \(b > d\) (a card can beat any other card of the same suit but of a lower rank). Two players play the game. Before the game starts, they receive exactly half of the deck each. The first player wins if for every card of the second player, he can choose his card that can beat it, and there is no card that is chosen twice (i. e. there exists a matching of the first player's cards with the second player's cards such that in each pair the first player's card beats the second player's card). Otherwise, the second player wins.Your task is to calculate the number of ways to distribute the cards so that the first player wins. Two ways are considered different if there exists a card such that in one way it belongs to the first player and in the other way it belongs to the second player. The number of ways can be very large, so print it modulo \(998244353\).
The only line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 500\)).Additional constraint on the input: \(m\) is even.
Print a single integer — the number of ways to distribute the cards so that the first player wins, taken modulo \(998244353\).