There is a mysterious town near Moonland City. The roads in the town form a $$$n \times m$$$ grid. Both ends of any road connect to the outside world.
But on a certain day, a mysterious force emerged and affected the town's traffic in a weird way. Any vehicle can only turn its direction at most $$$k$$$ $$$(k \geq 0)$$$ times (in any of the four directions, include the one it comes from) from the time it drives into the town to the time it drives out of the town. When the vehicle's remaining turning chances is zero, it can only go straight ahead until it drives out of the town from the end of the road it is on. $$$k$$$ will change every morning.
Mayor Brz bought $$$nm$$$ advanced steering devices and installed one at every intersection. Using the device, a vehicle can change its direction in any of the four directions without consuming its own turning chances. But this device requires a large amount of electricity, and the town cannot afford turning on all the devices. Mayor Brz quickly came up with a solution: every morning, according to the $$$k$$$ that day, turn on as few devices as possible, so that a vehicle entering the town from any of the ends can exit from any of the ends too.
The following figure shows a case where $$$n=m=5$$$ and $$$k=1$$$. The dot on the intersection means the device at that intersection is turned on. The red path enters the town from end $$$A$$$ and exits the town from end $$$B$$$. It first consumed its only chance to turn and then used all the three devices. However, it is impossible for a vehicle to enter from end $$$A$$$ and exit from end $$$C$$$. So this is not a valid solution.
Mayor Brz easily designed an algorithm to accomplish the task. But out of curiosity, he also wants to know how many different solutions there are to arrange devices for a given $$$k$$$. (Two solutions are considered different when and only when there is a certain intersection with different device states).
This problem later left a strong mark in the study of mathematics, historically known as Brz-Problem, or Problem-B for short.
Since the answer may be large, please output the answer modulo $$$998244353$$$.
The first line contains three integers $$$n,m,q$$$ $$$(1\leq n,m,q\leq 10^6)$$$, denoting the number of rows and columns of the roads, and the number of queries, respectively. Each of the next $$$q$$$ lines contains an integer $$$k$$$ $$$(0\leq k\leq 10^6)$$$, indicating the maximum number of times a car can be turned by mysterious forces in this query.
Output $$$q$$$ lines in total. The $$$i$$$-th line contains an integer indicating the result for the $$$i$$$-th query modulo $$$998244353$$$.
2 2 3 0 1 2
4 4 1
3 5 2 1 0
390 2025
