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\)