某人热爱拆。可是 SEU 没有那么多东西给他拆，于是他开始学习拆数。三下五除二，数被拆成了一堆质因子。保洁大妈来了，某人慌了，赶紧把这些数拼装起来。那一刹那，他想用一种特殊的方式记录下这一刻。
给定一个很大的数 NNN（拆成若干个质因子给出），求它所有因子的乘积对 109+710^9 + 7109+7 取模的结果。
请注意本题不同寻常的时间限制！
第一行包含一个正整数 n(1≤n≤105)n(1\le n \le 10^5)n(1≤n≤105)。
第二行包含 nnn 个正整数 p1,p2,...,pnp_1,p_2,...,p_np1,p2,...,pn，表示 N=∏i=1npiN=\prod_{i=1}^n p_iN=∏i=1npi。保证对任意 i∈[1,n]i \in [1,n]i∈[1,n]，pip_ipi 是质数且 1≤pi≤1061 \le p_i \le 10^61≤pi≤106。
输出一个正整数，表示 NNN 的所有因子的乘积对 109+710^9 + 7109+7 取模的结果。
样例输入
2 2 3
样例输出
36
