곱으로 분해하기

자연수 $n$개의 곱으로 표현된 자연수 $m$이 주어진다. $m$을 자연수 $n$개의 곱으로 분해하는 경우의 수를 구하라. 분해한 $n$개의 수를 모두 곱하면 $m$이 되어야 하고, 원소 구성이 같아도 순서가 다르면 서로 다른 경우로 센다.

예를 들어 $m = 15$이고 $n = 2$이면 $(1, 15)$, $(3, 5)$, $(5, 3)$, $(15, 1)$의 네 가지로 분해할 수 있다.

입력으로 주어진 $n$개의 수 자체도 하나의 분해로 센다. 경우의 수가 매우 크므로 답을 $1000000009$로 나눈 나머지를 출력한다.

첫째 줄에 자연수 $n$이 주어진다. ($1 \le n \le 500$)

둘째 줄에 자연수 $n$개가 공백을 사이에 두고 주어진다. 각 수는 $10^9$ 이하이다.

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