1869번 - 육각형

길이가 정수인 여러 개의 막대기가 있다. 막대기들 중에는 서로 길이가 같은 것도 있고, 다른 것도 있다. 이 중에서 여섯 개의 막대기를 골라 적당한 순서로 이어서 육각형 모양을 만들고 싶다. 여러 개의 막대기를 일직선으로 붙여 더 긴 막대기를 만들거나, 막대기를 더 짧은 길이로 조각낼 수는 없다. 또한, 육각형에 있는 여섯 개의 내각의 크기가 모두 같도록 하고 싶다.

위의 그림은 모든 내각의 크기가 같도록 만든 육각형의 예이다. 왼쪽의 육각형에서 알 수 있듯 막대기의 길이가 모두 같지 않다고 하더라도 주어진 조건을 만족하도록 육각형 모양을 만들 수 있는 경우도 있다.

막대기의 길이에 대한 정보가 주어졌을 때, 조건을 만족하면서 만들 수 있는 서로 다른 육각형의 개수를 구하는 프로그램을 작성하시오. 육각형을 회전하거나 뒤집어서 모양이 같아지는 경우는 하나의 육각형으로 생각한다.

첫째 줄에는 막대기의 개수 N(6 ≤ N ≤ 80)이 주어진다. 다음 줄에는 막대기의 길이를 나타내는 N개의 자연수가 빈 칸을 사이에 두고 주어진다. 막대기의 길이는 1,000,000을 넘지 않는 자연수이다.

첫째 줄에 조건을 만족하면서 만들 수 있는 서로 다른 육각형의 개수를 출력한다.