Problem Statement

You are given $\,N\,$ digits $\,c_1, c_2 \ldots , c_N\,$. Each $\,c_i \, (i=1, 2, \ldots , N)\,$ is one of the digits from 1 to 9.
Split these digits into $\,2\,$ groups and concatenate each group in an arbitrary order to form $\,2\,$ decimal numbers $\,X, Y\,$.

More formally, it is as follows.
Let $\,c_i'\,$ be the number corresponding to the digit $\,c_i \, (i=1, 2, \ldots , N)\,$. Given a choice of a permutation $\,P=(p_1, p_2, \ldots , p_N)\,$ of length $\,N\,$ and an integer $\,k\,(1 \leq k \leq N-1)\,$, $\,X, Y\,$ are defined as $\,X = \displaystyle{\sum_{i=1}^{k} c_{p_i}' 10^{k-i} } , Y = \displaystyle{\sum_{i=k+1}^{N} c_{p_i}' 10^{N-i} }\,$.

Find the minimum value of $\,|X-Y|\,$.
Since the answer can be very large, output the answer modulo $\,998244353\,$.

Constraints

• $\,N\,$ is an integer
• $\,2 \leq N \leq 2 \times 10^5\,$
• $\,c_i\,$ is one of 1 2 3 4 5 6 7 8 9

Input

The input is given from standard input in the following format.

$N$
$c_1$ $c_2$ $\cdots$ $c_N$

Output

Output the answer modulo $\,998244353\,$.

Sample

3
4 1 8

6

4
6 2 8 7

4

6
3 1 4 1 5 9

4