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\)