시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 12 4 3 37.500%

문제

홍준이와 명우는 수열을 이용한 신기한 게임을 즐겨한다. 처음에 홍준이는 자연수 N개로 이루어진 수열 A를 임의로 만든다. 그리고 명우도 홍준이처럼 수열 S를 만든다.

게임은 N번의 라운드로 진행된다. i번째 라운드에서 홍준이는 명우가 만든 수열의 i번째 원소 S[i] (1 <= i <= N) 보다 크지 않은 수 하나를 자신이 만든 수열 A에서 지워야한다. 만약 지울 수 있는 수가 없으면 홍준이는 지게 되고, 홍준이가 모든 라운드를 마치면 홍준이는 이기게 된다.

명우가 만든 수열 S가 주어졌고 홍준이가 최적의 전략으로 진행할 때, 홍준이가 이길 수 있는 수열 A의 개수를 구하자.

입력

문제에서 설명한 자연수 N이 주어진다. (1 <= N <= 200) 다음 N개의 줄에 수열 S에 대한 정보가 주어진다. i+1번째 줄에 주어지는 수는 S[i]이다. (1 <= S[i] <= 10^9)

출력

주어진 수열 S에 대해서 홍준이가 게임에 이길 수 있는 수열 A의 개수를 출력한다. 단, 답이 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 구하자.

예제 입력

2
1
2

예제 출력

3

힌트

홍준이가 이길 수 있는 수열 A로 (1,1), (1,2), (2,1)이 가능하다.

출처

  • 문제의 오타를 찾은 사람: corea
  • 문제를 번역한 사람: myungwoo