Today we will read on this article – Beautiful arrangement in C ++: If we have integer n from 1 to n. We will define a beautiful arrangement as an array that is fully constructed by these n numbers if one of the following is true for ith the position in this array (1 <= i <= N) –

• In the ith position the number can be divided by i.
• i is divisible by the number in the ith position.

Example

#include <bits/stdc++.h>
using namespace std;
class program{
   public:
   int ans;
   void solve(vector <bool>& visited, int end, int pos = 1){
      if(pos == end + 1){
         ans++;
         return;
      }
      for(int i = 1; i <= end; i++){
         if(!visited[i] && (pos % i == 0 || i % pos == 0)){
            visited[i] = true;
            solve(visited, end, pos + 1);
            visited[i] = false;
         }
      }
   }
   int countArrangement(int N) {
      ans = 0;
      vector <bool> visited(N);
      solve(visited, N);
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.countArrangement(2));
}

Input

3

Output

3