No.381 名声値を稼ごう Extra

レベル : / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 52
作問者 : LayCurseLayCurse

2 ProblemId : 923 / 出題時の順位表

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$ で割った余りを出力してください.

サンプル

サンプル1
入力
12
出力
2

本文中に書かれている例です.
普通にクリアし続けると得られる名声値は $22$ ですが,うまくすれば $24$ の名声値が得られるので,答えは $24-22 = 2$ となります.

サンプル2
入力
123456789123456789
出力
31

入力が32ビット整数型には収まらないことに注意してください.
入力が $64$ ビット整数型にも収まらないことに注意してください.

提出ページヘ