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

• 1) f(f(…f(1)…)) = 1 (단, f는 총 A₁개)
• 2) f(f(…f(2)…)) = 2 (단, f는 총 A₂개)
• …
• N) f(f(…f(N)…)) = N (단, f는 총 A_N개)

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

입력 형식

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

두 번째 줄에는 조건에 해당되는 N개의 양의 정수 A₁, A₂, …, A_N이 주어진다. (1 ≤ A_i ≤ 1,000,000)

출력 형식

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

예제 입력 1

4
3 6 9 12

예제 출력 1

10

예제 입력 2

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

예제 출력 2

20922789888000