시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 21 8 8 42.105%

문제

n개의 양수들의 곱으로 구성된 하나의 자연수 m이 주어집니다. 이 때, m을 n개의 수로 분해하는 경우의 수를 출력하는 프로그램을 작성하세요. 분해한 수들을 다시 곱하였을 때에 m이 되어야 하며, 원소의 구성은 같더라도 순서가 다른 분해는 다른 경우의 수로 간주합니다.

예를 들어 m = 15이고 n = 2라면, (1, 15), (3, 5), (5, 3), (15, 1) 총 4가지로 분해가 가능합니다.

입력 그 자체도 하나의 분해가 될 수 있으며, 경우의 수가 매우 크기 때문에 답을 1000000009로 나눈 나머지를 출력하세요.

입력

첫째 줄에는 하나의 양의 정수 n이 주어진다. n은 500 이하의 자연수입니다.

둘째 줄에는 n개의 자연수들이 공백을 사이에 두고 주어집니다. 이 자연수들은 10억 이하입니다.

출력

첫째 줄에 m을 분해하는 경우의 수를 1000000009로 나눈 나머지를 출력하세요.

예제 입력 1

3
1 1 2

예제 출력 1

3