Weapon Selection

DLS is a young man who loves playing games. Today, he saw N weapons from a friend, where the i-th weapon has power value i (for i = 1, 2, \(\dots, N\)).

After a long observation, he decided to buy some of these weapons. However, he wants to be able to combine the powers of the purchased weapons (by adding or subtracting them any number of times) to form any integer. For example, if he buys a weapon with power 3, he can form any multiple of 3: \(\dots, -6, -3, 0, 3, 6, \dots\).

Thus, he wants to choose a subset of weapons such that every integer can be represented as an integer linear combination of the power values of the bought weapons. In other words, if the chosen subset is \(S\), then the greatest common divisor \(\gcd(S) = 1\) (note that the empty subset is not allowed).

Your task is to calculate the number of ways to choose a non-empty subset \(S \subseteq \{1, 2, \dots, N\}\) such that \(\gcd(S) = 1\). Since the answer can be very large, output it modulo \(10^9+7\).

inputFormat

The input consists of a single line containing one integer N \( (1 \leq N \leq 10^6)\), the number of weapons.

outputFormat

Output a single integer, which is the number of valid subsets modulo \(10^9+7\).

sample

1

1