Description

给一个数组，求出数组乘积的因子数量。

这个答案可能很大，因此你需要输出答案对 $10^9+7$ 取模的结果。

Format

Input

第一行输入一个正整数 $n(1 \leq n \leq 10^6)$ 。

第二行输入 $n$ 个正整数 $a_i(1 \leq a_i \leq 10^6)$ ，表示数组。

Output

输出一个整数表示答案。

Samples

4
1 2 3 4

8

1,2,3,4,6,8,12,24，共8个。

Limitation

1s, 1024KiB for each test case.