You are given $N$ line segments. Print the number of subsets of these lines that form a regular polygon. A polygon is regular if and only if all of the edges of it are of equal length.

Input format

• The first line contains $N$. 
• The second line contains N numbers denoting the length of the line segments.

Output format

Print the answer modulo $10^9+7$.

Constraints
$1 \le N \le 10^6\\ 1 \le Ai \le 10^8$