Note

This problem is a version of 名声値を稼ごう with stronger constraints.
Due to the characteristics of the languages, it may be difficult to get accepted with C++, Java, or C#. We recommend answering in Ruby or Python.

Problem Statement

Quests in a certain game can be cleared any number of times, and clearing one earns you fame points.
A certain quest in that game gives $N$ fame points on the first clear, and the fame points obtained are halved (rounded down) with each clear.
That is, if the fame points obtained the first time are $12$, the fame points obtained on the $1$st, $2$nd, … clear are $12, 6, 3, 1, 0, 0, \ldots$.
Therefore, in total, you get $12 + 6 + 3 + 1 = 22$ fame points.

However, if you clear the quest using a character with a certain skill, the fame points obtained are doubled, but in exchange the fame points obtained on all subsequent clears become $0$.
For example, if you clear normally the $1$st time and clear using that character the $2$nd time, the fame points obtained are $12 + 2 \times 6 + 0 + 0 + \cdots = 24$.

Write a program to find the maximum number of extra fame points you can gain by making good use of the character with the skill, compared to the case where you never use the character with the skill.

Input

$N$

$1 \leq N \leq 10^{1000000}$

Output

Output the maximum number of extra fame points modulo $1004535809$.

Sample

12

2

123456789123456789

31