#P18143. Knocker

Knocker

Knocker

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

众所周知,Walter 是那个会敲门的人。但你知道吗,他可以对任意正整数 xx 用力度 xx 敲门。

他有一个正整数数组 a1,a2,…,ana_1,a_2,\dots,a_n。如果他以力度 xx 敲门,那么对每个 1≤i≤n1\le i\le n,aia_i 都会被替换成 ai mod xa_i\bmod x。

Walter 可以敲任意多次门(包括零次)。请求出他能够得到的不同数组 a1,a2,…,ana_1,a_2,\dots,a_n 的数量。答案可能很大,请对 998244353998244353 取模。

这里 x mod yx\bmod y 表示 xx 除以 yy 的余数。例如 6 mod 3=06\bmod 3=0,6 mod 4=26\bmod 4=2。

输入格式

第一行一个整数 nn(1≤n≤5001\le n\le 500)。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n(1≤ai≤5001\le a_i\le 500)。

输出格式

输出一个整数,表示可达的不同数组数对 998244353998244353 取模的结果。

样例 1

输入:

1
5

输出:

4

可以得到的数组为 [5],[2],[1],[0][5],[2],[1],[0]。

样例 2

输入:

2
6 5

输出:

7

可以得到的数组为 [6,5],[2,1],[1,0],[0,5],[0,2],[0,1],[0,0][6,5],[2,1],[1,0],[0,5],[0,2],[0,1],[0,0]。

样例 3

输入:

5
1 2 4 8 16

输出:

69