Counting Mirko's Winning Configurations

Mirko and Slavko play the following game. First, Mirko selects an arbitrary set S of pairs \(\{a,b\}\) chosen from the integers \([1,N]\) satisfying \(a < b\) and \(\gcd(a,b)=1\) (i.e. the numbers in each pair are coprime). Then Slavko should choose an integer \(x\) with \(2\le x\le N\) such that for every chosen pair \(\{a,b\}\) at least one of the following holds:

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

If Slavko is unable to find such an \(x\) then Mirko wins. Your task is to count the number of different selections (that is, different subsets \(S\) of qualifying coprime pairs) for which Mirko wins. Since the answer can be very large, print it modulo \(10^9\).

Note on the problem formulation: A set \(S\) is considered a winning configuration for Mirko if for every \(x,\, 2\le x\le N\) there exists at least one pair \(\{a,b\}\in S\) with \(a < x \le b\) (i.e. the pair "straddles" the boundary \(x\)). For example, if \(N=5\) and Mirko chooses \(S=\{\{1,2\},\{3,4\}\}\), then for \(x=3\) we have \(1<3\le2\) is false for the first pair but \(3<3\le4\) is also false; indeed one can check that Slavko can find an \(x\) satisfying the condition so that such an \(S\) does not let Mirko win.

Explanation: Let \(M\) be the set of all coprime pairs \(\{a,b\}\) with \(1\le a < b \le N\). Mirko wins with his chosen set \(S\) if and only if for every possible boundary \(x\) (with \(2 \le x \le N\)) there is at least one pair \(\{a,b\}\) in \(S\) such that \(a < x\) and \(b \ge x\). One may solve the problem via inclusion–exclusion. It turns out (after some derivation) that the answer can be computed by the formula: \[ \text{answer} = 2^{|M|} - \sum_{L=2}^{N}2^{f(L)+g(L)} + \sum_{L=2}^{N-1}2^{f(L)+g(L+1)} \quad (\bmod\, 10^9), \] where:

• \(f(L)\) is the number of coprime pairs with maximum element less than \(L\);
• \(g(R)\) is the number of coprime pairs with minimum element at least \(R\).

This formula counts exactly the number of winning subsets \(S\) (note that the empty set is not winning because Slavko can always choose an \(x\) in that case).

inputFormat

The input consists of a single integer \(N\) (with \(N\ge 2\)), representing the maximum number in the range \([1,N]\).

outputFormat

Output a single integer, the number of winning configurations for Mirko modulo \(10^9\).

sample

2

1