平方因数有几个

题目描述

给定一个正整数标准质因数分解中的 k 个非负指数 e1,…,ek，计算该整数的完全平方正因数数量。

输入格式

第一行输入 k，满足 1≤k≤15。第二行输入 k 个指数，满足 0≤ei≤60，并保证答案不超过10^18。

输出格式

输出 ∏(⌊ei/2⌋+1)。

样例

输入

1
0

输出

1