For a multiset $A$ consisting of positive integers, let $a = a_1, a_2, \dots, a_n$ be an arbitrary permutation of its elements. Define a sequence $b = b_0, b_1, \dots, b_n$ of length $n+1$ such that $b_i = \lfloor \frac{\sum_{j=1}^i a_j}{10} \rfloor$, where the empty sum is $0$. Let $f(A) = \max_{a} |\{b\}|$, where $|S|$ denotes the size of the set $S$ (the number of distinct elements in the sequence $b$). In other words, for a given $A$, we want to find the maximum number of distinct values in $b$ over all possible permutations $a$. Specifically, $f(\emptyset) = 1$.

Given a multiset $A$, calculate the sum of $f(B)$ for all distinct subsets $B$ of $A$, modulo $998244353$.

Two multisets $X$ and $Y$ are considered distinct if and only if there exists a value $v$ such that the number of occurrences of $v$ in $X$ is different from that in $Y$.

Input

The first line contains an integer $n$, the size of the multiset $A$. The next line contains $n$ integers $a_1, a_2, \dots, a_n$, representing the multiset $A = \{a_1, a_2, \dots, a_n\}$.

Output

A single line containing the sum of $f(B)$ for all distinct subsets $B$ of $A$, modulo $998244353$.

Examples

Input 1

1
1

Output 1

2

Input 2

6
1 1 2 2 3 3

Output 2

31

Input 3

12
1 2 3 4 5 6 7 8 9 10 11 12

Output 3

18228

Constraints

For all test cases, $n \le 2000$ and $1 \le a_i \le 12$.