K. Minimum Sum
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given $$$n$$$ $$$n$$$-digit numbers (there may be leading zeros).

For each $$$i$$$ in increasing order ($$$1 \le i \le n$$$), you must choose $$$j \neq i$$$ and perform the following operation:

  • $$$a_i := a_j $$$ (assign the $$$j$$$-th number to the $$$i$$$-th number).

Find the minimum sum of all $$$n$$$ numbers modulo $$$998244353$$$ after performing all the operations (you need to find the minimum sum first, then print it modulo $$$998244353$$$).

Input

The first line consists of one integer $$$n \:(2 \le n \le 700)$$$.

The following $$$n$$$ lines consist of the numbers $$$a_i$$$ (where $$$a_i$$$ has exactly $$$n$$$ digits).

Output

The only line consists of one integer, which is the minimum sum modulo $$$998244353$$$ after performing all the operations.

Examples
Input
4
3142
5310
0341
3423
Output
1364
Input
3
032
102
999
Output
306