Step1.求单个数的因子个数

根据素数分解定理，我们知道一个数的约数个数是一个数的唯一分解定理表示法后的每个质数的指数 + 1 的 累乘积 例如: 60 = 2^2 * 3 * 5 = 2^2 * 3^1 * 5^1 那么因数个数就是 (2 + 1) * (1 + 1) * (1 + 1) = 12

Step2.求单个数的阶乘的因子的个数

N! = 1 * 2 * 3 * ... * N

题目描述

小红拿到了$n$个正整数$a_i$，她希望你求出这些数的阶乘全部来在一起生成的大数有多少个因子。你能帮帮她吗?

输入描述

第一行输入一个正整数$n$。

第二行输入几个正整数$a_i$，用空格隔开

$1\le n\le 2\times 10^5$

$1\le a_i\le 10^6$

输出描述

一个整数，代表这个乘积的因子数量，由于答案可能过大，请对$10^9+7$取模.

样例

输入

3
1 2 3

输出

6

说明

1!*2!*3!=12,共有1,2,3,4,6,12六个因子。