<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:
    def specialPerm(self, nums: List[int]) -> int:

        mod = 10 ** 9 + 7

        adjacent = {}
        for i in range(len(nums)):
            adjacent.setdefault(i, set())
        for i, A in enumerate(nums):
            for j, B in enumerate(nums):
                if i >= j:
                    continue
                if (A % B == 0) or (B % A == 0):
                    adjacent[i].add(j)
                    adjacent[j].add(i)
        print(f'{adjacent=}')
        for i in range(len(nums)):
            if len(adjacent[i]) == 0:
                print(f'NO. Nothing adjacent to {i=}')
                return 0
        
        # len(nums) <= 14, therefore we can store used-nums-indexes as a bitmask
        @cache
        def tuple_to_bitmask(S: tuple) -> int:
            answer = 0
            for index in range(15):
                if index in S:
                    # print(f'+{index=} ({2 ** index})')
                    answer += (2 ** index)
            return answer

        # @cache    # sets are an unhashable object
        def set_to_bitmask(S: set) -> int:
            # or, could use frozenset() instead
            return tuple_to_bitmask(tuple(S))
        
        @cache
        def bitmask_to_set(Bitmask: int) -> set:
            bits = tuple(
                reversed(
                    f'{Bitmask:b}'
                )
            )
            # print(f'{Bitmask=} {Bitmask:b} {bits}')
            answer = set()
            for index, bit in enumerate(bits):
                if bit == '1':
                    answer.add(index)
            return answer
        
        # print(f'{set_to_bitmask(bitmask_to_set(10000))=}')
        # print(f'{bitmask_to_set(set_to_bitmask({1, 3, 7, 11}))=}')

        @cache
        def permutations_recursive(BitmaskRemaining: int, priorIndex: int) -> int:
            # print(f'permutations_recursive({BitmaskRemaining},{priorIndex})')
            SetRemaining = bitmask_to_set(BitmaskRemaining)
            if priorIndex is None:
                SetAdjacent = set(adjacent.keys())
            else:
                SetAdjacent = adjacent[priorIndex]
            SetAllowed = SetRemaining.intersection(SetAdjacent)
            # print(f'{SetAllowed=}: {SetRemaining} X {SetAdjacent}')
            if not SetRemaining:
                # success!
                return 1
            elif not SetAllowed:
                # no possible next move
                return 0
            return sum([
                permutations_recursive(
                    set_to_bitmask(
                        SetRemaining - {A}
                    ),
                    A
                )
                for A in SetAllowed
            ])
            
        SetOfEverything = set(range(len(nums)))
        BitmaskOfEverything = set_to_bitmask(SetOfEverything)
        # print(f'{SetOfEverything=} {BitmaskOfEverything=}')
        answer = permutations_recursive(BitmaskOfEverything, None)

        return answer % mod

5466