You are given a positive integer N. Find the number of the pairs of integers u and v (0≦u,v≦N) such that there exist two non-negative integers a and b satisfying a xor b=u and a+b=v. Here, xor denotes the bitwise exclusive OR. Since it can be extremely large, compute the answer modulo 10^9+7.

Constraints

* 1≦N≦10^{18}

Input

The input is given from Standard Input in the following format:


N


Output

Print the number of the possible pairs of integers u and v, modulo 10^9+7.

Examples

Input

3


Output

5


Input

1422


Output

52277


Input

1000000000000000000


Output

787014179
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

n = input()
n = bin(n)[2:]

def func(dig, val1, val2):
    for i in range(dig):
        v1 = val1 * 2 + val2
        v2 = val2 * 2 + val1
        val1, val2 = v1, v2
    return val2

ans = 0
val1 = 0
val2 = 1
for i in range(len(n)):
    if n[i] == '1':
        ans += func(len(n) - i - 1, val1, val1 + val2)
        val1 = val1 + val2
    else:
        val2 = val1 + val2
print (ans + val2) % (10 ** 9 + 7)