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