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\).