沫沫最近在研究勾股定理。对于两个正整数 与 ，若存在正整数 使得 ，且 与 互质，则称 为一个互质勾股数对。
有一天，沫沫得到了 根木棍，其长度都是正整数，她准备从中挑选出若干根木棍来玩拼图游戏，为了使拼出的图案有凌乱美，她希望挑选出的木棍中任意两根的长度均不是互质勾股数对。现在，沫沫想知道有多少种满足要求的挑选木棍的方案。由于答案可能很大，你只要输出答案对 取模的结果。
从文件 input.txt 中读入数据，输入文件第一行是一个正整数 ，表示共有多少根木棍。
input.txt
输入文件第二行是用空格隔开的 个正整数 ，其中对 ， 表示第 根木棍的长度。
输出文件 output.txt 仅包含一个非负整数，表示满足要求的挑选木棍的方案数对 取模的结果。
output.txt
4 5 12 35 5
8
与 是互质勾股数对，故满足要求的挑选木棍的方案有 种，即：，，，，，，，。
对于 的数据，对任意 ，； 对于另外 的数据，对任意 ，； 对于剩下 的数据，对任意 ，； 对于 的数据，。
没有写明提示 没有写明来源（题面来自洛谷）
