問題文
新婚のA君とBさんは結婚のお祝いに1からNまでの数字が1つずつ書かれたN枚のカードを貰いました。
2で割れる数は別れを意味するため縁起が悪いと考えるBさんは、それぞれのカードに書かれた数字を2で割り切れなくなるまで割ることにしました。
例えば、24と書かれていたカードは2で3回割ることで3と書かれたカードに変わりました。
最終的にN枚のカードに書かれた数字の総和はいくつになったか求めてください。
ただし、答えは非常に大きくなることがあるので、答えを1000000007で割ったあまりを出力してください。
制約
1 ≦ N ≦ 109
入力
入力は以下の標準入力から与えられる
| N |
部分点
この問題には以下のように部分点が設定されている
1 ≦ N ≦ 1000 を満たすテストケースに正解した場合は部分点100点が与えられる。
全てのテストケースに正解した場合は追加で200点が与えられ、300点満点となる。
出力
操作後のN枚のカードの数字の総和を 109+7 で割ったあまりを出力せよ。
入力例1
| 4 |
出力例1
| 6 |
入力例2
| 32 |
出力例2
| 342 |
入力例3
| 123456789 |
出力例3
| 268738047 |