<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:
        n = len(nums)
        MOD = 10**9 + 7

        # dp[mask][i] represents the number of special permutations of the numbers in mask (a bitmask)
        # where the last number in the permutation is nums[i].
        dp = [[0] * n for _ in range(1 << n)]

        # Initialize dp for the base case where the permutation contains only one number.
        for i in range(n):
            dp[1 << i][i] = 1

        # Iterate over all possible bitmasks.
        for mask in range(1 << n):
            for i in range(n):
                if mask & (1 << i):
                    # Try to extend the permutation by adding another number j.
                    for j in range(n):
                        if not mask & (1 << j) and (nums[j] % nums[i] == 0 or nums[i] % nums[j] == 0):
                            dp[mask | (1 << j)][j] = (dp[mask | (1 << j)][j] + dp[mask][i]) % MOD

        # Sum up all the permutations that use all the numbers.
        return sum(dp[(1 << n) - 1][i] for i in range(n)) % MOD

# Example usage:
solution = Solution()
print(solution.specialPerm([2, 3, 6]))  # Output: 2
print(solution.specialPerm([1, 4, 3]))  # Output: 2
5316