S-Grundy game#644

S-Grundy game

2 seconds

64 megabytes

Medium

Let $S$ be a set of nonnegative integers. Define the sequence $G_{S} (n)$ G_S(n) ( $n > 0$ n > 0) by the formula:

where $mex A$ is the minimal nonnegative integer not in $A$ , and $a xor b$ is the result of bitwise addition of $a$ and $b$ modulo $2$ .

We say that a set $S$ is good if $G_{S} (n + 4) = G_{S} (n)$ G_S(n+4) = G_S(n) for $n > 4$ n > 4, and the values $G_{S} (n)$ G_S(n) for $n = 1, 2, 3, 4, 5, 6, 7, 8$ n = 1, 2, 3, 4, 5, 6, 7, 8 are $0, 0, 0, 1, 0, 2, 1, 3$ 0, 0, 0, 1, 0, 2, 1, 3 respectively.

Given $n \geq 0$ n \geq 0, find the number of good sets whose elements do not exceed $n$ , modulo $1 0^{9} + 7$ 10^9 + 7.

Input

The only line of the input contains a nonnegative integer $n$ ( $n \leq 1 0^{18}$ n \leq 10^{18}).

Output

Output a single integer: the answer to the problem.

Examples

Example 1

Loading

G_{S} (n)

n > 0

G_{S} (n + 4) = G_{S} (n)

n > 4

G_{S} (n)

n = 1, 2, 3, 4, 5, 6, 7, 8

0, 0, 0, 1, 0, 2, 1, 3

n \geq 0

1 0^{9} + 7

n \leq 1 0^{18}