S-Grundy game

Let S - is a certain set of nonnegative integers. Let us construct a sequence G_S(n) (n > 0) using the formula

where mex A - is the least nonnegative integer which does not belong to the set A, and a xor b - is a result of bitwise addition of numbers a and b modulo 2.

A set S well be called beautiful, if G_S(n+4)=G_S(n) when n > 4, and values G_S(n) are equal 0,0,0,1,0,2,1,3 when n=1,2,3,4,5,6,7,8 correspondingly.

You are given n ≥ 0 and required to find the number of beautiful sets with elements not exceeded n, and yields this number modulo10^9+7.

Input

The only line of thei nput file contains a nonnegative integer n ≤ 10^18.

Output

In the output file you should write the answer of the task.

Examples