@jagmag said in beautiful arrangements:

Lucy has N numbers from 1 to N. Her arrangement of those numbers is called a beautiful arrangement if any of the following is true:

The number present at the ith position is divisible by i.

i is divisible by the number present at the ith position.

For a given N, how many beautiful arrangements are possible?

Constraints

1 < N < 20

Function

You are given a function arrangement that takes N as its argument and will return the total number of all possible beautiful arrangements.

Sample Input

2

Sample Output

2

Explanation

The number of possible beautiful arrangements for N=2 will be:

1 2

2 1

Consider the arrangement [1, 2] then:

number present at 1st position (i = 1) is 1, and 1 is divisible by i.

number present at 2nd position (i = 2) is 2, and 2 is divisible by i.

Consider the arrangement [2, 1] then:

number present at 1st position (i = 1) is 2, and 2 is divisible by i.

number present at 2nd position (i = 2) is 1, and i is divisible by 1.