Help Walter solve his final problem.
For a positive integer , define highest\_bit(n) as the largest number , such that 2^i \leq n. Also define highest\_bit(0) = -1.
You are given a positive integer . Find the number of multisets of positive integers, which satisfy the following conditions:
All elements of are nonnegative powers of .
The sum of elements of is .
There is no way to split elements of into two groups so that highest\_bit(S_1) = highest\_bit(S_2), where S_1 is the sum of the elements in the first group, and S_2 is the sum of the elements in the second group.
Solve this problem for X = 1, 2, \ldots, n.
Since the answers can be very large, output them modulo .
The only line of the input contains a single integer (1 \leq n \leq 10^6).
Output integers: answers to the problem for X = 1, 2, \ldots, n, modulo .
Example