Problem

There is a list of consecutive numbers beginning with 1. An arrangement of these numbers is called "beautiful" if at least one of the following is true for each position using 1-based indexing:

1. The number at position i is divisible by i
2. i is divisible by the number at position i

Determine how many beautiful arrangements are possible for a given n integers.

Example

n = 5

The possible beautiful arrangements are: [1, 2, 3, 4, 5] [2, 1, 3, 4, 5] [3, 2, 1, 4, 5] [4, 2, 3, 1, 5] [5, 2, 3, 4, 1] [4, 1, 3, 2, 5] [1, 4, 3, 2, 5] [3, 4, 1, 2, 5] [2, 4, 3, 1, 5] [5, 4, 3, 2, 1]

In the first arrangement, both conditions hold for all elements, so each equals the value at index i, so each is divisible by i. In subsequent arrangements, at least one of the conditions is satisfied at each position.

Function Description

Complete the function arrangements in the editor with the following parameter(s): n: an integer

Returns

n: the number of beautiful arrangements possible.

Sample Input 2, the input is n = 4.

Here are the 8 valid permutations:

[1, 2, 3, 4] [2, 1, 3, 4] [3, 2, 1, 4] [4, 2, 3, 1] [1, 4, 3, 2] [4, 1, 3, 2] [3, 4, 1, 2] [2, 4, 3, 1] Since every single position follows either the "value is divisible by index" or "index is divisible by value" rule, [4, 1, 3, 2] counts as 1 of the 8 valid arrangements!