<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

        def recurse(nums, prev, dp, mask, idx):
            if idx == len(nums):
                return 1
            
            if dp[prev+1][mask] != -1:
                return dp[prev+1][mask]
            
            total = 0
            for i in range(len(nums)):
                if (not (mask & (1 << i))and (prev==-1 or nums[i]%nums[prev]==0 or nums[prev]%nums[i]==0)):
                    total = (total + recurse(nums, i, dp, mask | (1<<i), idx+1)) % MOD
            
            dp[prev+1][mask] = total
            return dp[prev+1][mask]
        
        maxMask = 2 ** (len(nums)) - 1
        dp = [[-1] * maxMask for _ in range(len(nums) + 1)]
        return recurse(nums, -1, dp, 0, 0)
            
        
    #     int calperm(const vector<int>& nums, int prev, int index, int mask, vector<vector<int>>& dp) {
    #     // Base case: all elements have been placed in the permutation
    #     if (index == nums.size()) {
    #         return 1;
    #     }
    #     // Check if the result for the current state has already been computed
    #     if (dp[prev + 1][mask] != -1) {
    #         return dp[prev + 1][mask];
    #     }
    #     int total = 0;
    #     // Try adding each remaining element to the permutation
    #     for (int i = 0; i < nums.size(); ++i) {
    #         // Skip if the element has already been included
    #         if (!(mask & (1 << i)) && (prev == -1 || nums[i] % nums[prev] == 0 || nums[prev] % nums[i] == 0)) {
    #             // Recursive call to calculate the number of special permutations with the current element included
    #             total = (total + calperm(nums, i, index + 1, mask | (1 << i), dp)) % MOD;
    #         }
    #     }
    #     // Store the computed result in the dp table for memoization
    #     dp[prev + 1][mask] = total;
    #     return total;
    # }

2010