00:00:00

Description

Editorial

Divisibility Compliant Permutations

MEDIUM30 pts

You are given a positive integer n representing a collection of integers from 1 to n (inclusive). Your task is to determine how many unique permutations of these integers satisfy a special divisibility compliance rule.

A permutation perm (1-indexed) is considered divisibility compliant if and only if, for every position i (where 1 ≤ i ≤ n), at least one of the following conditions holds:

The value at position i (i.e., perm[i]) is evenly divisible by i
The position index i is evenly divisible by perm[i]

In mathematical terms, for each position i: either perm[i] % i == 0 OR i % perm[i] == 0 must be true.

Return the total count of all such divisibility compliant permutations that can be formed using integers from 1 to n.

Example

Input

n = 2

Output

2

Explanation

There are exactly two compliant permutations:

Permutation [1, 2]: • Position 1: perm[1] = 1. Since 1 is divisible by 1 (1 % 1 == 0), this position is compliant. • Position 2: perm[2] = 2. Since 2 is divisible by 2 (2 % 2 == 0), this position is compliant.

Permutation [2, 1]: • Position 1: perm[1] = 2. Since 2 is divisible by 1 (2 % 1 == 0), this position is compliant. • Position 2: perm[2] = 1. Since 2 is divisible by 1 (2 % 1 == 0), this position is compliant.

Both permutations satisfy the divisibility rule at every position, so the answer is 2.

Example

Input

n = 1

Output

1

Explanation

With only one integer, the only possible permutation is [1]. At position 1, the value 1 divides 1 evenly (1 % 1 == 0), so this permutation is compliant. The total count is 1.

Example

Input

n = 3

Output

3

Explanation

For n = 3, we need to evaluate all 6 permutations of [1, 2, 3]:

[1, 2, 3]: Position 1 ✓ (1%1=0), Position 2 ✓ (2%2=0), Position 3 ✓ (3%3=0) — Compliant [1, 3, 2]: Position 1 ✓ (1%1=0), Position 2 ✗ (3%2≠0 and 2%3≠0), Position 3 ✗ — Not Compliant [2, 1, 3]: Position 1 ✓ (2%1=0), Position 2 ✓ (2%1=0), Position 3 ✓ (3%3=0) — Compliant [2, 3, 1]: Position 1 ✓ (2%1=0), Position 2 ✗ (3%2≠0 and 2%3≠0), Position 3 ✗ — Not Compliant [3, 2, 1]: Position 1 ✓ (3%1=0), Position 2 ✓ (2%2=0), Position 3 ✓ (3%1=0) — Compliant [3, 1, 2]: Position 1 ✓ (3%1=0), Position 2 ✓ (2%1=0), Position 3 ✗ — Not Compliant

Three permutations satisfy the divisibility compliance rule, so the answer is 3.

Accepted0/0·0% Acceptance

Constraints

1 ≤ n ≤ 15

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

n =

Loading problem...

101

00:00:00

Description

Editorial

Divisibility Compliant Permutations

MEDIUM30 pts

A permutation perm (1-indexed) is considered divisibility compliant if and only if, for every position i (where 1 ≤ i ≤ n), at least one of the following conditions holds:

The value at position i (i.e., perm[i]) is evenly divisible by i
The position index i is evenly divisible by perm[i]

In mathematical terms, for each position i: either perm[i] % i == 0 OR i % perm[i] == 0 must be true.

Return the total count of all such divisibility compliant permutations that can be formed using integers from 1 to n.

Example

Input

n = 2

Output

2

Explanation

There are exactly two compliant permutations:

Both permutations satisfy the divisibility rule at every position, so the answer is 2.

Example

Input

n = 1

Output

1

Explanation

With only one integer, the only possible permutation is [1]. At position 1, the value 1 divides 1 evenly (1 % 1 == 0), so this permutation is compliant. The total count is 1.

Example

Input

n = 3

Output

3

Explanation

For n = 3, we need to evaluate all 6 permutations of [1, 2, 3]:

Three permutations satisfy the divisibility compliance rule, so the answer is 3.

Accepted0/0·0% Acceptance

Constraints

1 ≤ n ≤ 15

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

n =

Divisibility Compliant Permutations

Hints

Divisibility Compliant Permutations

Hints