Counting Constrained Subsets

Given a positive integer n (with 1 ≤ n ≤ 10⁵), count the number of subsets S of the set {1,2,…,n} satisfying the constraint that if a number x is in S then neither 2x nor 3x can be in S. In other words, for every x, the subset S must not contain any pair (x, 2x) or (x, 3x). Output the answer modulo 10⁹+1.

The original homework problem asked this for the set {1,2,3,4,5} but here we generalize it to any n up to 10⁵.

This problem can be recast as counting independent sets in a graph on the vertex set {1,2,…,n} where an edge exists between x and 2x (if 2x ≤ n) and between x and 3x (if 3x ≤ n). Notice that if both endpoints of any such edge are chosen then the constraint is violated. However, observe that the constraint is only active in the forward (multiplicative) direction; indeed, if x is chosen then 2x (or 3x) must not be chosen, but the converse is not forced. It turns out that every positive integer can be uniquely expressed as

\( k\times2^{a}\times3^{b} \) with \(\gcd(k,6)=1\).

This observation decomposes the set {1,2,…,n} into components determined by the k part; for each such k (with \(1 \le k \le n\) and \(\gcd(k,6)=1\)) the numbers in the component are of the form \( k\,2^{a}3^{b} \) with nonnegative integers a and b satisfying \(k\,2^{a}3^{b}\le n\). In this two‐parameter (a,b) grid the rule becomes: if a cell (a,b) is chosen then the cell (a+1,b) (corresponding to multiplying by 2) and the cell (a,b+1) (multiplying by 3) cannot be chosen. Such a structure is amenable to dynamic programming using a row–by–row state–transition (where the row index is a and the number of valid columns in each row depends on n, k, and a). Finally, the answer is the product over the components (for all valid k) of the number of independent sets in that sub–grid, modulo 10⁹+1.

Your task is to implement an algorithm that computes this number modulo 10⁹+1. (Note: The intended solution uses a decomposition by numbers coprime with 6 and a DP on a grid whose rows correspond to the power of 2, and each row’s length is governed by the maximum power of 3 allowed.)

inputFormat

The input consists of a single line containing one integer n (1 ≤ n ≤ 10⁵).

outputFormat

Output a single integer: the number of subsets of {1,2,…,n} that satisfy the constraint (if x is chosen then 2x and 3x are not chosen), modulo 10⁹+1.

sample

1

2