526

class Solution {
int ans=0;
int mask = 0;
public:
    int countArrangement(int n) {
        dfs(n, 1);
        return ans;
    }

    void dfs(int n, int pos){
        if(pos > n) ans++;
        for(int i=1; i<=n; i++){
            bool isSet = (mask & (1<<i));
            if(!isSet && (i%pos == 0 || pos%i == 0)){
                mask |= (1<<i);
                dfs(n, pos+1);
                mask ^= (1<<i);
            }
        }
    }
};