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:
Each subtask consists of one testcase.
Input consists of one integer, n.
Print the answer modulo 109 + 7 in a single line.