Felina#12926

Felina

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:

Solve this problem for X = 1, 2, \ldots, n.

Since the answers can be very large, output them modulo .

Input

The only line of the input contains a single integer (1 \leq n \leq 10^6).

Output

Output integers: answers to the problem for X = 1, 2, \ldots, n, modulo .

Examples

Example

Loading
Loading