Note

この問題は，名声値を稼ごうの制約強化版です．
言語の特性上C++,Java,C#で正答するのは困難かもしれません。Ruby,Pythonでの回答をおすすめします。

問題文

あるゲームのクエストは何回でもクリアすることができ，クリアすることで名声値を得ることができます．
そのゲームのあるクエストは，初回にクリアすると $N$ だけの名声値が得られ，クリアするごとに得られる名声値が（小数点以下切り捨てで）半分になっていきます．
つまり，初回に得られる名声値が $12$ であれば，$1$ 回目，$2$ 回目，…にクリアした時に得られる名声値は $12, 6, 3, 1, 0, 0, \ldots$ となります．
よって，合計では，$12 + 6 + 3 + 1 = 22$ の名声値を得られることになります．

ところが，あるスキルを持っているキャラクターを利用してクリアすると，得られる名声値の値が倍になり，その代わりに次回以降にクリアした時に得られる名声値は $0$ になります．
例えば，$1$ 回目は普通にクリアし，$2$ 回目はそのキャラクターを利用してクリアすると，得られる名声値は $12 + 2 \times 6 + 0 + 0 + \cdots = 24$ となります．

常にスキルを持ったキャラクターを利用しない場合と比べて，うまくスキルを持っているキャラクターを利用すると，いくらの名声値を余分に得ることができるか，最大値を求めるプログラムを書いてください．

入力

$N$

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

出力

余分に得られる名声値の最大値を $1004535809$ で割った余りを出力してください．

サンプル

12

2

123456789123456789

31