Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 &lt;= i &lt;= n), either of the following is true:


	perm[i] is divisible by i.
	i is divisible by perm[i].


Given an integer n, return the number of the beautiful arrangements that you can construct.

&nbsp;
Example 1:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1


Example 2:

Input: n = 1
Output: 1


&nbsp;
Constraints:


	1 &lt;= n &lt;= 15


class Solution:
    def countArrangement(self, n: int) -> int:
        self.count = 0
        self.backtrack(n, 1, [])
        return self.count
        
    def backtrack(self, N, idx, temp):
        if len(temp) == N:
            self.count += 1
            return
        
        for i in range(1, N+1):
            if i not in temp and (i % idx == 0 or idx % i == 0):
                temp.append(i)
                self.backtrack(N, idx+1, temp)
                temp.pop()
class Solution {
    int N;
    Integer[][] memo;
    public int countArrangement(int n) {
        this.N = n;
        memo = new Integer[n+1][1<<N];
        return permute(1, 0);
    }

    private int permute(int index, int mask)
    {
        if (mask == (1<<N)-1)
            return 1;
        if (memo[index][mask] != null)
            return memo[index][mask];
        int res = 0;
        for (int i = 1; i <= N; i++)
        {
            if ((mask & (1<<(i-1))) == 0 && (index % i == 0 || i % index == 0))
            {
                mask |= (1<<(i-1));
                res += permute(index+1, mask);
                mask ^= (1<<(i-1));
            }
        }
        return memo[index][mask]=res;
    }
}
class Solution {
public:
    int ans = 0;
    bool isBeautiful(vector<int> &v) {
        int i = v.size() - 1;
        if (v[i] % (i + 1) == 0 || (i + 1) % v[i] == 0) return true;
        return false;
    }

    void solve(int n, vector<int> &p, vector<bool> &seen) {
        if (p.size() == n) {
            ans++;
            return;
        }
        for (int i = 1; i <= n; i++) {

            if (seen[i]) continue;
            p.push_back(i);

            if (isBeautiful(p)) {
                seen[i] = true;
                solve(n, p, seen);
                seen[i] = false;
            }
            p.pop_back();
        }
    }
    int countArrangement(int n) {

        vector<int> p;
        vector<bool> seen(n + 1, false);
        solve(n, p, seen);

        return ans;
    }
};
var countArrangement = function(n) {
    let result = 0;
    const visited = Array(n + 1).fill(false);
    const dfs = (next = n) => {
        if (next === 0) {
            result += 1;
            return;
        }

        for (let index = 1; index <= n; index++) {
            if (visited[index] || index % next && next % index) continue;
            visited[index] = true;
            dfs(next - 1);
            visited[index] = false;
        }
    };

    dfs();
    return result;
};
Beautiful Arrangement