It's a lazy Friday evening, perfect time to throw some shrimps on the barbie!
Luca has an infinite number of shrimp, and he plans to cook some on his barbecue grill. Luca's grill can be represented as an $$$n\times m$$$ grid of squares, where each square can hold up to one shrimp. However, due to his grill being of the upside-down variety, it has a unique quirk. If any $$$2\times 2$$$ subgrid of squares contains an odd number of shrimp, then all the shrimp in the subgrid will burn!
Luca was wondering how much this quirk affects his ability to cook and wanted to know the number of ways he could place shrimp on the grill that could result in them burning. However, Luca has to get back to grilling his shrimps, so he doesn't have any more time to spend thinking about this problem. You, on the other hand, have plenty of time. Please help Luca count the number of ways to place shrimp on the grill such that at least one shrimp will burn. Since this number could be large, output it modulo $$$998244353$$$.
The input contains two integers $$$n$$$ and $$$m$$$ $$$(2\leq n, m\leq 2000)$$$ — the dimensions of the barbecue grill.
Output a single integer, the number of ways to place shrimp on the grill that could result in a shrimp burning, modulo $$$998244353$$$.
2 2
8
2 3
48
5 8
444591027
For the first test case, the 8 possible ways are:
where a 1 represents a shrimp and a 0 represents an empty square.
