12938번 - 곱으로 분해하기

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로 나눈 나머지를 출력하세요.