Irreducible Fractions

시간 제한3초메모리 제한2048 MB

요약

서로 다른 네 인덱스를 골라 두 값의 곱을 나머지 두 값의 곱으로 나눈 분수가 기약분수가 되는 경우의 수를 센다.

난이도: 어려움10점 중 8점
유형: 정수론, 조합론, 수학, 정렬
정답자: 아직 제출이 없습니다

문제

Given an array $a$ consisting of $n$ positive integers, find the number of quadruples of distinct indices $(i, j, k, l)$ such that the following fraction is irreducible:

$\frac{a\_i \cdot a\_j}{a\_k \cdot a\_l}\text{.}$

입력

The first line contains an integer $n$ ( $4 \leq n \leq 2000$ ) denoting the length of the array. The second line contains $n$ integers $a\_i$ ( $1 \leq a\_i \leq 10^{12}$ ), the elements of the array.

출력

Output a single integer: the number of quadruples satisfying the given condition.

예제2

예제 1
입력
```
4
1 1 1 1
```
예상 출력
```
24
```
예제 2
입력
```
6
10 11 2 4 5 7
```
예상 출력
```
96
```