시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 41 26 21 72.414%

문제

민혁이는 집합 S = 1, 2, …, N에 대해서 함수 f : S -> S를 만들었다. 민혁이가 만든 함수는 재미있는 성질을 갖고 있다.

  • 1) f(f(…f(1)…)) = 1 (단, f는 총 A1개)
  • 2) f(f(…f(2)…)) = 2 (단, f는 총 A2개)
  • N) f(f(…f(N)…)) = N (단, f는 총 AN개)

민혁이는 이런 성질을 만족하는 서로 다른 함수를 총 몇 개나 만들 수 있을지 궁금해졌다. 민혁이를 도와 A1, A2, …, AN이 주어졌을 때 서로 다른 함수를 총 몇 개 만들 수 있는지 구하는 프로그램을 작성하여라. 두 함수 g, h에 대해서 g(x)≠h(x)를 만족하는 x가 있다면 g, h는 서로 다른 함수이다.

입력

첫 번째 줄에 정의역의 크기 N이 주어진다. (3 ≤ N ≤ 16)

두 번째 줄에는 조건에 해당되는 N개의 양의 정수 A1, A2, …, AN이 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫 번째 줄에 조건을 만족하도록 함수를 만드는 방법의 수를 출력한다.

예제 입력

4
3 6 9 12

예제 출력

10

예제 입력 2

16
720720 720720 720720 720720 720720 720720 720720 720720 720720 720720 720720 720720 720720 720720 720720 720720

예제 출력 2

20922789888000

힌트

출처

Contest > FunctionCup > FunctionCup 2016 FC번