Note

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

問題文

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

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

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

入力

$N$

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

出力

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

サンプル

12

2

123456789123456789

31