<p>You are given a&nbsp;<strong>0-indexed</strong>&nbsp;integer array&nbsp;<code>nums</code>&nbsp;containing&nbsp;<code>n</code>&nbsp;<strong>distinct</strong> positive integers. A permutation of&nbsp;<code>nums</code>&nbsp;is called special if:</p>

<ul>
	<li>For all indexes&nbsp;<code>0 &lt;= i &lt; n - 1</code>, either&nbsp;<code>nums[i] % nums[i+1] == 0</code>&nbsp;or&nbsp;<code>nums[i+1] % nums[i] == 0</code>.</li>
</ul>

<p>Return&nbsp;<em>the total number of special permutations.&nbsp;</em>As the answer could be large, return it&nbsp;<strong>modulo&nbsp;</strong><code>10<sup>9&nbsp;</sup>+ 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,3,6]
<strong>Output:</strong> 2
<strong>Explanation:</strong> [3,6,2] and [2,6,3] are the two special permutations of nums.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,4,3]
<strong>Output:</strong> 2
<strong>Explanation:</strong> [3,1,4] and [4,1,3] are the two special permutations of nums.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= nums.length &lt;= 14</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    ans = 0
    def specialPerm(self, nums: List[int]) -> int:
        neigh = [[] for _ in range(len(nums))]
        for index1, num1 in enumerate(nums):
            for index2, num2 in enumerate(nums):
                if index1 < index2 and (num1 % num2 == 0 or num2 % num1 == 0):
                    neigh[index1].append(index2)
                    neigh[index2].append(index1)
        print(neigh)

        mod = pow(10, 9) + 7
        length = len(nums)
        # print((1 << length) - 1)
        dp = {}
        # for index in range(length):
        #     dp[(index, 1 << index)] = 1
        def dfs(last, bitmask):
            # print(last, bitmask)
            key = (last, bitmask)
            if key in dp:
                return dp[key]
            if bitmask == (1 << length) - 1:
                return 1
            ans = 0
            for n in neigh[last]:
                if bitmask | (1 << n) != bitmask:
                    ans += dfs(n, bitmask | (1 << n))
            dp[key] = ans
            return ans
        for index in range(length):
            dfs(index, 1 << index)
        ans = 0
        for index in range(length):
            if (index, 1 << index) in dp:
                ans = (ans + dp[(index, 1 << index)]) % mod
        # print(dp)
        return ans
1484