You are given an integer array A of size x denoting the prime powers of an integer N. $A_i$ denotes the power of $i^{th}$ prime in the prime factorization of N. To make it more clear, $A_1$ will denote the power of 2 in the prime factorization of N, $A_2$ will denote the power of 3 in the prime factorization of N and so on.

Consider a number P equals to the product of all the divisors of N. You have to find the number of divisors of P. Output it modulo $10^9 + 7$.

Input Format:
The first line contains an integer, x ($1 \le x \le 10^6$) denoting the size of array A. Next line contains x space separated integers, denoting the array A ($0 \le A_i \le 10^9$).

Output Format:
Print one integer, denoting the number of divisors of P, modulo $10^9 + 7$.