When Bruce learned set theory, he assigned a homework question to his students.

Given a positive integer ~N~, find the number of subsets of the whole set ~\{1, 2, \dots, N\}~ that satisfies the following constraint: if an integer ~x~ is in the subset, then the integers ~2x~ and ~3x~ are not in the subset. For example, given ~N = 4~, the whole set is ~\{1, 2, 3, 4\}~. The number of subsets satisfying the constraint is ~8~, including the empty set: ~\emptyset~, ~\{1\}~, ~\{1, 4\}~, ~\{2\}~, ~\{2, 3\}~, ~\{3\}~, ~\{3, 4\}~, and ~\{4\}~.

Input Specification

The input will consist of one integer ~N~ ~(1 \le N \le 100\,000)~.

Output Specification

Output the number of subsets that satisfy the above constraints mod ~1\,000\,000\,001~ ~(= 10^9+1)~.

Sample Input

4

Sample Output

8