Problem Description

Mirko and Slavko are playing a game. First, Mirko selects several pairs of coprime numbers from the range \(1 \dots N\). For example, when \(N = 5\), Slavko can choose from \(\big\{\{1,2\},\{3,4\},\{2,5\},\{3,5\},\cdots\big\}\).

Next, it's Slavko's turn. He needs to find an \(x \in [2, N]\) such that for every pair \(\{a, b\}\), one of the following conditions is satisfied:

• \(a, b < x\)
• \(a, b \ge x\)

For example, if Mirko selected \(\big\{\{1,2\},\{3,4\}\big\}\), then \(x\) could be 3.

If Slavko cannot find such an \(x\), Mirko wins. Your task is to calculate the total number of different scenarios where Mirko wins, modulo \(10^9\).

Input Format

The first line contains an integer \(N\).

Output Format

The first line should output an integer, which is the total number of different scenarios where Mirko wins, modulo \(10^9\).

Sample Input and Output

Sample Input #1

2

Sample Output #1

1

Sample Input #2

3

Sample Output #2

5

Sample Input #3

4

Sample Output #3

21

Notes

[Sample 1 Explanation]

Slavko can only choose \(\big\{\{1,2\}\big\}\).

[Sample 2 Explanation]

One of Slavko's possible choices is \(\big\{\{1,2\},\{1,3\}\big\}\).

[Data Range]

For \(100\%\) of the data, \(1 \le N \le 20\).

[Problem Source]

This problem is translated from COCI 2015-2016 CONTEST #6 T4 PAROVI.

This problem is scored according to the original COCI settings, with a maximum score of 120.

见题面 Input 部分

见题面 Output 部分