K. Knocker
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
I am the danger. A guy opens his door and gets shot, and you think that of me? No. I am the one who knocks!
—Walter White, Breaking Bad

It's well-known that Walter is the one who knocks. But did you know that he can knock with strength $$$x$$$ for every positive integer $$$x$$$?

He has an array $$$a_1, a_2, \ldots, a_n$$$ of positive integers. If he knocks with strength $$$x$$$, then, for each $$$1 \leq i \le n$$$, $$$a_i$$$ will be replaced with $$$a_i \bmod x$$$.

How many different arrays $$$a_1, a_2, \ldots, a_n$$$ can Walter achieve by knocking any number of times? As the number can be very large, output it modulo $$$998244353$$$.

Here $$$x \bmod y$$$ denotes the remainder of $$$x$$$ when dividing by $$$y$$$. For example, $$$6 \bmod 3 = 0$$$, and $$$6 \bmod 4 = 2$$$.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 500$$$)  — the length of the array.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 500$$$)  — the elements of the array.

Output

Output a single integer  — the number of different arrays Walt can achieve by knocking.

Examples
Input
1
5
Output
4
Input
2
6 5
Output
7
Input
5
1 2 4 8 16
Output
69
Note

In the first sample, you can get the following arrays: $$$[5], [2], [1], [0]$$$.

In the second sample, you can get the following arrays: $$$[6, 5], [2, 1], [1, 0], [0, 5], [0, 2], [0, 1], [0, 0]$$$.