Please do this in Python.

Game of Numbers

Mirko and Slavko are playing a game. Mirkos turn is first and he chooses a non-empty set of pairs of numbers between 1 and N (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 N = 5, Mirko could have chosen the following set of pairs: {{1, 2}, {3, 4}, {2, 5}, {3, 5}}.

Slavkos turn is second and his goal is to find a partition for Mirkos set of pairs. Mirkos set of pairs has a partition if an integer x from the set {2, 3, ..., N} exists such that, for each pair {a, b}, one of the following holds: a, b < x a, b x

For example, a set of pairs {{1, 2}, {3, 4}} has a partition x = 3. If a partition exists, Slavko will surely find it.

Mirko wins if Slavko cant 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 1000000000.

Input Format: The first line of input contains the integer N. 1 N 20

Constraints: Time limit : 1 sec

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

Sample Input 1: 2

Sample Output 1: 1

Sample Input 2: 3

Sample Output 2: 5

Explanation: Clarification of the first example: The only set of pairs that meets the given requirements is {{1,2}}. Clarification of the second example: An example of a set that meets the given requirement is {{1,3},{1,2}}.

PLEASE ATTEMPT THIS IN PYTHON.

Also please do not copy paste the previous answers from older post on chegg because those code doesn't work.