Decompose into a Product

Time limit2sMemory limit512 MB

Summary

Given m as a product of n factors (n ≤ 500, each up to 1e9), count ordered n-tuples of positive integers whose product is m, modulo 1e9+9.

Level: Medium7 of 10
Topics: Number theory, Combinatorics, Math, Prefix sum
Solved: No attempts yet

Problem

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$ .

Input

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$ .

Output

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

Examples3

Example 1
Input
```
3
1 1 2
```
Expected output
```
3
```
Example 2
Input
```
2
3 5
```
Expected output
```
4
```
Example 3
Input
```
1
1
```
Expected output
```
1
```