Background

给定$n$个正整数$a_i$，请你输出这些数的乘积的约数个数，答案对$10^9+7$取模。

Input

第一行包含整数$n$。

接下来$n$行，每行包含一个整数$a_i$。

输入

Output

第一行包含整数$n$。

接下来$n$行，每行包含一个整数$a_i$。

Samples

3
2
6
8

12

Limitation

$1≤n≤100,$

$1≤ai≤2×10^9$