Given an array A of length n (n<=25) (Ai<=1e9). You have to construct a full binary tree with n nodes numbered from 1 to n, and if i is the parent of j and k, Ai=Gcd(Aj,Ak) must be satisfied. Two binary trees are considered different if two indexes i,j exist such that i is parent of j in this tree but not in the other. Count the number of distinct way to build the tree (in mod 1e9+7).

I tried to think of dp bitmask approach but the constraint for n seems too large for it. Is it solvable with DNC or not? Please help me.