Decompose into a Product

A natural number $m$ is given as the product of $n$ natural numbers. Count the ways to decompose $m$ into $n$ natural numbers. The $n$ numbers you write down must multiply back to $m$, and two decompositions that use the same elements in a different order count as different ways.

For example, if $m = 15$ and $n = 2$, there are four decompositions: $(1, 15)$, $(3, 5)$, $(5, 3)$, $(15, 1)$.

The $n$ numbers given in the input also count as one decomposition. The count grows very large, so print it modulo $1000000009$.

The first line contains a natural number $n$ ($1 \le n \le 500$).

The second line contains $n$ natural numbers separated by spaces. Each of them is at most $10^9$.

Print the number of ways to decompose $m$, modulo $1000000009$, on the first line.