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

# C: Represents a combination of elements picked as an integer. LSB = 1 means 0th index number is picked. 
# i, e, j: These represent the indexes of the numbers in nums array

PRIME = int(1e9 + 7)

# (C, e): ans
mem = dict()

def is_unary(C):
    # Check if the number is non-zero and has only one bit set
    return (C != 0) and (C & (C - 1) == 0)

def is_present(C: int, index: int):
    return (C & (1<<index) ) > 0

def remove(C: int, index: int):
    return C - (1<<index)

def zing(i:int, j: int, nums: list[int]):
    if i == j:
        return False
    return nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0

def solve(C, e, nums) -> int:
    # = Number of special permutations with the combination/selection `C` from nums & ending with the number with index `e`.
    if not is_present(C, e):
        return 0
    if is_unary(C):
        return 1
    if (C, e) in mem:
        return mem[(C, e)]
    
    # Remove e from C:
    C1 = remove(C, e)
    ans = 0
    
    # Find out all permutations will all possible endings of C1, Let's say it ends with `i`.
    # If e zings with i, count `{{C1 ending with i} ending with e}` for the current answer.
    for i in range(len(nums)):
        if i != e and is_present(C1, i):
            if zing(i, e, nums):                
                temp = solve(C1, i, nums)
                # print(f"zing: {nums[e]}, {nums[i]} | solve({bin(C1)}, {nums[i]}) = {temp}")
                ans = (ans + temp) % PRIME
            
    mem[(C, e)] = ans
    return ans


# Driver
def solveMain(C, nums):
    ans = 0
    for e in range(len(nums)):
        if is_present(C, e):
            temp = solve(C, e, nums)
            #print(f"Triggering: {bin(C)} | {nums[e]} | {temp}")
            ans = (ans + temp) % PRIME
    return ans
    
    
class Solution:
    def specialPerm(self, nums: List[int]) -> int:
        mem.clear()
        N = len(nums)
        # reversal does not matter, but its useful to view the print statements. 
        ans = solveMain((1<<N) - 1, list(reversed(nums))) 
    
        # print(mem)
        return ans
4189