题目描述

徐老师有一个包含 $n$ 个整数的序列 $a$，分别为 $a_1,a_2,a_3 \dots a_n$

他可以选择一个正整数 $k$ 进行一个特殊的操作—— $a \% k$

也就是将 $a$ 序列中的所有数字 $\% k$

现在徐老师想知道，如果他可以任意选择 $k$ 进行 $a \% k$，并且不限操作次数

最终可能产生多少种不同的序列？

输入格式

输入第一行包含一个整数 n 表示数字个数

输入第二行包含 $n$ 个整数，分别为 $a_1,a_2,a_3 \dots a_n$

输出格式

输出一个答案表示不同的序列个数，由于答案可能很大，请你将答案对 $1e9+7$ 取模

数据范围

对于所有的数据满足： $0 \leq n, a_i \leq 500$

其中数据点分别满足以下情况

测试点	特殊性质
$1\sim 2$	$n = 2$
$3\sim 5$	$a_i \leq 20$
$6\sim 10$	$a_i = i$

样例输入1

3
1 3 4

样例输出1

6

样例解释1

可以执行 $a\%5$，得到序列 $\{1,3,4\}$

可以执行 $a\%4$，得到序列 $\{1,3,0\}$

可以执行 $a\%3$，得到序列 $\{1,0,1\}$

可以执行 $a\%2$，得到序列 $\{1,1,0\}$

可以执行 $a\%1$，得到序列 $\{0,0,0\}$

可以依次执行 $a\%4,a\%3$，得到序列 $\{1,0,0\}$

样例输入2

10
1 2 3 4 5 6 7 8 9 10

样例输出2

256