Define a non-empty positive integer multi-set as "Good" iff the product of all elements in the set is the square of some positive integer $x$, and the "Good" set has a weight of $x$.
Let the set $SS$ be defined as the multi-set of all non-empty subsets of the multi-set $S$.
For example, when $S=\{1_1,1_2,8\}$, $SS=\{\{1_1\},\{1_2\},\{8\},\{1_1,1_2\},\{1_1,8\},\{1_2,8\},\{1_1,1_2,8\}\}$
Now, given a multi-set $S$ of size $N$, Chino wants to know the sum of the weights of all "Good" sets in $SS$. Output the answer modulo $10^9+7$.
输入格式
The first line contains a positive integer $N(1\leq N \leq 1000)$ — the size of $S$.
The next line contains $N$ positive integers $S_i(1\leq S_i \leq 1000)$ — each element in the set $S$.
输出格式
Only one line with a non-negative integer, representing the answer modulo $10^9+7$.
输入样例
复制
6
1 2 6 3 7 7
输出样例
复制
111
数据范围与提示
"Good" sets include $\{1\},\{2,3,6\},\{7_1,7_2\},\{1,2,3,6\},\{1,7_1,7_2\},\{2,3,6,7_1,7_2\},\{1,2,3,6,7_1,7_2\}$
$\sqrt{1^2}+\sqrt{6^2}+\sqrt{7^2}+\sqrt{6^2}+\sqrt{7^2}+\sqrt{42^2}+\sqrt{42^2}=111$```