Problem Brief

Count Divisible Permutations

NEW GRADOA

SDE-1

Suppose you have n integers from 1 through n. A permutation of those n integers is considered a Divisible Permutation if for every i, where 1 <= i <= n, either of the following is true:

perm[i] is divisible by i.

i is divisible by perm[i].

Given an integer n, find the total number of the valid Divisible Permutations.

Note - you may want to refer to LC 810

1Example 1

Input

n = 2

Output

Explanation

The first Divisible Permutation is [1,2]: permutation[1] = 1 is divisible by i = 1 permutation[2] = 2 is divisible by i = 2 The second Divisible Permutation is [2,1]: permutation[1] = 2 is divisible by i = 1 i = 2 is divisible by permutation[2] = 1

Constraints

Limits and guarantees your solution can rely on.

1 <= n <= 15

Draft autosaves locally

public int countDivisiblePermutations(int n) {
  // write your code here
}

Input

Output