402242: GYM100705 C3 Dawn of the planet of the Rastas
Memory Limit：1024 MB
Time Limit：15 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
C3. Dawn of the planet of the Rastastime limit per test15 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output
Due to the cruelties of Mike, Rastas attacked his country (to help its people of course) and they're moving forward to the capital.
Rastas' army has 2n - 1 soldiers and the strength of soldier number i is the number of set bits (bits equal to 1) in binary representation of number i (soldiers are numbered from 1 to 2n - 1).
If the greatest common divisor of numbers a and b is gcd(a, b), we know that strength of this army which we show with S is equal to:
As the minister of Mike, it's your duty to calculate S modulo 109 + 7.
Subtasks:
- Subtask C1: n = 14
- Subtask C2: n = 1234
- Subtask C3: n = 12345678
Each subtask consists of one testcase.
Input consists of one integer, n.
OutputPrint the answer modulo 109 + 7 in a single line.
Examples