数字染色
题号：NC221827
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红拿到了一个由正整数组成的数组，她准备把这个数组上的某些数染成红色。
但是有一个限制，染成红色的所有的数的 gcd （最大公约数）必须大于 1 。
小红想知道，自己有多少种不同的染色方案？
我们定义，若两种方案染色的数的数量不同，或者有两个数的染色状态不同，那么则视为两种不同的方案。
这个方案数可能过大，请对 取模。

输入描述:

第一行一个正整数  ，代表数组的大小。
第二行有  个正整数 ，表示数组。

输出描述:

染红色数字的方案数，对  取模。
示例1

输入

复制 
4
2 3 6 2

输出

复制 
9

说明

共有 9 个方案：{1}，{2}，{3}，{4}，{1,3}，{2,3}，{3,4}，{1,4}，{1,3,4}。其中以上为所选数的下标。
示例2

输入

复制 
4
2 3 1 7

输出

复制 
3

说明

共有 3 个方案：{1}，{2}，{4}