We are given an array $nums$ of positive integers.
A special number is a number that is not divisible by the square of any number$(>1)$.
Example:
$12$ is not a special number, because it is divisible by $4$(which is $2^2$).
$18$ is not a special number, because it is divisible by $9$(which is $3^2$).
$35,6,15$ are special numbers.
You have to find the number of the non-empty different subsets of the array such that the product of elements in it is a special number. Return answer modulo $10^9 + 7$.

Input format

• The first line contains an integer $N$, where $N$ is denoting the size of the array.
• The second line contains $N$ space-separated integers denoting array $nums$.

Output format

• Print the number of the non-empty different subsets.

Constraints

• $1 \leq N \leq 4\times10^4$
• $1 \leq nums[i]\leq 30$