Fancy Stack

Little Fiona has a collection of $$$n$$$ blocks of various sizes $$$a_1, a_2, \ldots, a_n$$$, where $$$n$$$ is even. Some of the blocks can be equal in size. She would like to put all these blocks one onto another to form a fancy stack.

Let $$$b_1, b_2, \ldots, b_n$$$ be the sizes of blocks in the stack from top to bottom. Since Fiona is using all her blocks, $$$b_1, b_2, \ldots, b_n$$$ must be a permutation of $$$a_1, a_2, \ldots, a_n$$$. Fiona thinks the stack is fancy if both of the following conditions are satisfied:

• The second block is strictly bigger than the first one, and then each block is alternately strictly smaller or strictly bigger than the previous one. Formally, $$$b_1 < b_2 > b_3 < b_4 > \ldots > b_{n-1} < b_n$$$.
• The sizes of the blocks on even positions are strictly increasing. Formally, $$$b_2 < b_4 < b_6 < \ldots < b_n$$$ (remember that $$$n$$$ is even).

Two stacks are considered different if their corresponding sequences $$$b_1, b_2, \ldots, b_n$$$ differ in at least one position.

Fiona wants to know how many different fancy stacks she can build with all of her blocks. Since large numbers scare Fiona, find this number modulo $$$998\,244\,353$$$.