Beautiful Arrangement

Given n integers labeled 1 to n, count the number of permutations where for each position i, the number at i is either divisible by i or i is divisible by the number at i.

Examples
Input: 1
Output: 1
Hints

Beautiful Arrangement

Given n integers labeled 1 to n, count the number of permutations where for each position i, the number at i is either divisible by i or i is divisible by the number at i.