C1. Dawn of the planet of the Rastas
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard 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