402241: GYM100705 C2 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

C2. 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
Input

Each subtask consists of one testcase.

Input consists of one integer, n.

Output

Print the answer modulo 109 + 7 in a single line.

Examples

Source/Category

加入题单

上一题 下一题 算法标签：