Competitions

# SEERC 2021

# Modulo Permutations

Given a natural number **n**, count the number of permutations (`p`

, _{1}`p`

, ..., _{2}`p`

) of the numbers from _{n}**1** to **n**, such that for each **i** (**1** ≤ **i** ≤ **n**), the following property holds: `p`

mod _{i}`p`

≤ _{i+1}**2**, where `p`

= _{n+1}`p`

._{1}

As this number can be very big, output it modulo `10`

+ ^{9}**7**.

#### Input

One integer **n** (**1** ≤ **n** ≤ `10`

).^{6}

#### Output

Output a single integer - the number of the permutations satisfying the condition from the statement,
modulo `10`

+ ^{9}**7**.

#### Example

For example, for **n** = **4** you should count the permutation [**4**, **2**, **3**, **1**] as **4** mod **2** = **0** ≤ **2**, **2** mod **3** = **2** ≤ **2**, **3** mod **1** = **0** ≤ **2**, **1** mod **4** = **1** ≤ **2**. However, you shouldn’t count the permutation [**3**, **4**, **1**, **2**], as **3** mod **4** = **3** > **2** which violates the condition from the statement.

Input example #1

1

Output example #1

1

Input example #2

2

Output example #2

2

Input example #3

3

Output example #3

6

Input example #4

4

Output example #4

16

Input example #5

5

Output example #5

40

Input example #6

1000000

Output example #6

581177467