In Setsuna's country, there are $$$n$$$ cities. They are arranged in ascending order on a number line. City $$$i$$$ is on the position $$$x_i$$$. The distance between city $$$i$$$ and city $$$j$$$ is $$$|x_i-x_j|$$$. Any two cities are in different positions. It is guaranteed that $$$n$$$ is an even number. There are $$$n-1$$$ roads at the beginning, and the $$$i$$$-th road is between city $$$i(1\le i \lt n)$$$ and city $$$i+1$$$.

Now, these $$$n$$$ cities want to establish relationships. The cities are divided into $$$\frac n2$$$ pairs $$$(a_i,b_i)(a_i \lt b_i)$$$. City $$$a_i$$$ will establish a relationship with $$$b_i$$$, then build a path between $$$a_i$$$ and $$$b_i$$$. A path between city $$$a$$$ and city $$$b$$$ covers road $$$a\rightarrow a+1, a+1 \rightarrow a+2, ..., b-1\rightarrow b$$$. Two schemes $$$A,B$$$ are called different if there exists a city $$$i$$$ that establishs a relationship with city $$$j$$$ in scheme $$$A$$$ but estabilishs a relationship with city $$$k$$$ in scheme $$$B$$$ and $$$j\not = k$$$.

But roads between neighboring cities sometimes get traffic jams when too many paths are built. In order to solve this problem, Setsuna will give the peak of every road in advance. The peak of the $$$i$$$-th road is $$$s_i$$$, indicating that no more than $$$s_i$$$ paths can cover road $$$i\rightarrow i+1$$$. If there is no road that the number of paths covering it exceeds its peak in a scheme, we call this scheme valid. The sum of the distances $$$S$$$ in a scheme equals to $$$\sum_{i=1}^{n/2} |x_{a_i}-x_{b_i}|$$$.

Now Setsuna wants to know, what is the sum of $$$S$$$ in all schemes. The answer could be large, please print the answer modulo $$$998244353$$$.