SOLVE
LATER
You are given a Deadpool set A which contains N unique integers.
The speciality of a Deadpool set is that if you remove a integer from the set it reappears magically, just like Deadpool's body parts. :3
Given this set you have to print number of unique Deadpool trees that can be made by using integers from that set.
Note : As the integers reappear magically, they can be used several times in a particular Deadpool Tree.
Properties of Deadpool tree:
Each node is either a leaf node or has exactly two children.
If a node is not a leaf node then it's value is exactly equal to the product of its children.
The value of each node is greater than '1'.
Constraints:
1<=N<=10^{6}
1<=A[i]<=10^{6}
It is guaranteed that numbers in the set are unique.
Input:
First line has a single number N.
Each of the following N lines has a single number denoting the values of numbers in the set A.
Output:
Print ans modulo 10^{9}+7 where ans is the number of unique Deadpool trees.
Problem Setter - Teja Vojjala
The contents of deadpool set are 2,3,4,6. If we remove a number from this set it reappears magically so the contents of the set are always 2,3,4,6 no matter what and we have an infinite supply of 2,3,4,6. The following are the only trees which satisfy the deadpool tree properties.
Note that in each tree each node is either a leaf node or a node with exactly two children whose values is same as the product of its children and value in each node is greater than 1.