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

输入描述:

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

输出描述:

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