<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:
    # https://leetcode.com/problems/special-permutations/solutions/3650420/beginner-friendly-2-methods-similar-questions-bit-mask-visited-array/
    MOD = int(1e9) + 7

    def helper(self, nums, preIdx, curIdx, msk, dp):
        if curIdx == len(nums):
            #  Base case: If we have reached the end of the numbers, there is only one special permutation which is []
            return 1

        if dp[preIdx + 1][msk] != -1:
            return dp[preIdx + 1][msk]

        total = self.MOD
        for ind in range(len(nums)):
            if msk & (1 << ind): # 当前index已经被用过，被标记在mask里面了。 
                continue

            if preIdx == -1 or nums[ind] % nums[preIdx] == 0 or nums[preIdx] % nums[ind] == 0:
                total += self.helper(nums, ind, curIdx + 1, msk | (1 << ind), dp) % self.MOD
                total %= self.MOD

        dp[preIdx + 1][msk] = total
        return total

    def specialPerm(self, nums):
        # 二维数组， [-3] * x 每一纬度。 x = mask可能的最大值
        dp = [[-1] * ((1 << 14) + 7) for _ in range(21)]
        return self.helper(nums, -1, 0, 0, dp) % self.MOD
21700