### 问题描述

小桥来到了一个神秘的魔法世界，这个世界中有着各种神奇的事物和力量。在这个世界中，有一个特殊的序列 $a$，小桥需要找到一些非空的子集，使得它们的乘积不等于任何整数的平方。

小桥想知道一共有多少种选择的方法。为了保护魔法世界的平衡，答案需要对 $998244353$ 取模。

输入格式

第一行输入一个整数 $n$（$1 \le n \le 10^5$），表示序列 $a$ 的长度。

第二行输入 $n$ 个整数 $a_i$（$1\le a_i \le 50$），表示序列 $a$ 中的元素。

输出格式

输出一个整数，表示选择方法的数量对 $998244353$ 取模后的结果。

样例输入

2
2 2

样例输出

2