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 是那个会敲门的人。但你知道吗,他可以对任意正整数 x 用力度 x 敲门。
他有一个正整数数组 a1,a2,…,an。如果他以力度 x 敲门,那么对每个 1≤i≤n,ai 都会被替换成 aimodx。
Walter 可以敲任意多次门(包括零次)。请求出他能够得到的不同数组 a1,a2,…,an 的数量。答案可能很大,请对 998244353 取模。
这里 xmody 表示 x 除以 y 的余数。例如 6mod3=0,6mod4=2。
输入格式
第一行一个整数 n(1≤n≤500)。
第二行 n 个整数 a1,a2,…,an(1≤ai≤500)。
输出格式
输出一个整数,表示可达的不同数组数对 998244353 取模的结果。
样例 1
输入:
1
5
输出:
4
可以得到的数组为 [5],[2],[1],[0]。
样例 2
输入:
2
6 5
输出:
7
可以得到的数组为 [6,5],[2,1],[1,0],[0,5],[0,2],[0,1],[0,0]。
样例 3
输入:
5
1 2 4 8 16
输出:
69