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