Mirko and Slavko are playing a game. Mirko’s turn is first and he chooses a **non-empty** set of pairs
of numbers between and (inclusive) under the condition that the numbers that comprise a pair
are mutually **relatively prime**. The numbers that comprise a pair must be different. For example,
for , Mirko could have chosen the following set of pairs: .

Slavko’s turn is second and his goal is to find a **partition** for Mirko’s set of pairs. Mirko’s set of pairs
has a **partition** if an integer from the set exists such that, for each pair , one of
the following holds:

For example, a set of pairs has a partition . If a partition exists, Slavko will surely find it.

Mirko wins if Slavko can’t find a partition for his set. Determine how many different sets of pairs exists that Mirko can initially choose and be sure of his victory. Given the fact that the total number of sets can be very large, output the number modulo .

#### Input

The first line of input contains the integer .

#### Output

The first and only line of output must contain the required number.

#### Sample Input 1

`2`

#### Sample Output 1

`1`

#### Explanation for Sample Output 1

The only set of pairs that meets the given requirements is .

#### Sample Input 2

`3`

#### Sample Output 2

`5`

#### Explanation for Sample Output 2

An example of a set that meets the given requirements is .

#### Sample Input 3

`4`

#### Sample Output 3

`21`

## Comments