N=int(eval(input()))

mod=10**9+7



ANSLIST=[1]

for i in range(61):

    ANSLIST.append((ANSLIST[-1]*3-1)%mod)



ANS=[1, 2, 4, 5]

ANSDICT=dict()

def ans(k):

    if 0<=k<=3:

        return ANS[k]

    if ANSDICT.get(k)!=None:

        return ANSDICT[k]

    for i in range(61):

        if k==2**i-2:

            return ANSLIST[i]-1

        if k==2**i-1:

            return ANSLIST[i]

        if 2**i-1>k:

            break

    x=k-(2**(i-1)-1)



    ANSDICT[k]=(ans(x-1)+ANSLIST[i-1]*2-ans(2**(i-1)-x-2)-1)%mod

    return ANSDICT[k]



print((ans(N)))
import sys

sys.setrecursionlimit(10**9)



N=int(eval(input()))

mod=10**9+7

DP=dict()

DP[(0,0)]=1#a+b,a^b

DP[(1,0)]=1

DP[(1,1)]=2



def ans(S,X):

    #print(S,X)

    if DP.get((S,X))!=None:

        return DP[(S,X)]

    if S==0:

        return 1

    #if X>S:

    #    return ans(S,S)

    



    DP[(S,X)]=(ans(S//2,X//2)+ans((S-1)//2,(X-1)//2)+ans((S-2)//2,(X-2)//2))%mod

    #一番下の桁をみて、bitが0,0の場合,1,0の場合,1,1の場合.

    #三つ目の場合は本来ans((S-2)//2,X//2)だが,今回扱うのはS=Xのときで,X>Sのときは0になるので,ans((S-2)//2,(X-2)//2)で良いはず.

    return DP[(S,X)]



print((ans(N,N)))

N = int(eval(input()))
mod = 10**9 + 7
ANSLIST = [1]
for i in range(61):
    ANSLIST.append((ANSLIST[-1] * 3 - 1) % mod)
ANS = [1, 2, 4, 5]
ANSDICT = dict()


def ans(k):
    if 0 <= k <= 3:
        return ANS[k]
    if ANSDICT.get(k) != None:
        return ANSDICT[k]
    for i in range(61):
        if k == 2**i - 2:
            return ANSLIST[i] - 1
        if k == 2**i - 1:
            return ANSLIST[i]
        if 2**i - 1 > k:
            break
    x = k - (2 ** (i - 1) - 1)
    ANSDICT[k] = (ans(x - 1) + ANSLIST[i - 1] * 2 - ans(2 ** (i - 1) - x - 2) - 1) % mod
    return ANSDICT[k]


print((ans(N)))

import sys

sys.setrecursionlimit(10**9)
N = int(eval(input()))
mod = 10**9 + 7
DP = dict()
DP[(0, 0)] = 1  # a+b,a^b
DP[(1, 0)] = 1
DP[(1, 1)] = 2


def ans(S, X):
    # print(S,X)
    if DP.get((S, X)) != None:
        return DP[(S, X)]
    if S == 0:
        return 1
    # if X>S:
    #    return ans(S,S)
    DP[(S, X)] = (
        ans(S // 2, X // 2)
        + ans((S - 1) // 2, (X - 1) // 2)
        + ans((S - 2) // 2, (X - 2) // 2)
    ) % mod
    # 一番下の桁をみて、bitが0,0の場合,1,0の場合,1,1の場合.
    # 三つ目の場合は本来ans((S-2)//2,X//2)だが,今回扱うのはS=Xのときで,X>Sのときは0になるので,ans((S-2)//2,(X-2)//2)で良いはず.
    return DP[(S, X)]


print((ans(N, N)))

+import sys + +sys.setrecursionlimit(10**9) -ANSLIST = [1] -for i in range(61): -    ANSLIST.append((ANSLIST[-1] * 3 - 1) % mod) -ANS = [1, 2, 4, 5] -ANSDICT = dict() +DP = dict() +DP[(0, 0)] = 1  # a+b,a^b +DP[(1, 0)] = 1 +DP[(1, 1)] = 2 -def ans(k): -    if 0 <= k <= 3: -        return ANS[k] -    if ANSDICT.get(k) != None: -        return ANSDICT[k] -    for i in range(61): -        if k == 2**i - 2: -            return ANSLIST[i] - 1 -        if k == 2**i - 1: -            return ANSLIST[i] -        if 2**i - 1 > k: -            break -    x = k - (2 ** (i - 1) - 1) -    ANSDICT[k] = (ans(x - 1) + ANSLIST[i - 1] * 2 - ans(2 ** (i - 1) - x - 2) - 1) % mod -    return ANSDICT[k] +def ans(S, X): +    # print(S,X) +    if DP.get((S, X)) != None: +        return DP[(S, X)] +    if S == 0: +        return 1 +    # if X>S: +    #    return ans(S,S) +    DP[(S, X)] = ( +        ans(S // 2, X // 2) +        + ans((S - 1) // 2, (X - 1) // 2) +        + ans((S - 2) // 2, (X - 2) // 2) +    ) % mod +    # 一番下の桁をみて、bitが0,0の場合,1,0の場合,1,1の場合. +    # 三つ目の場合は本来ans((S-2)//2,X//2)だが,今回扱うのはS=Xのときで,X>Sのときは0になるので,ans((S-2)//2,(X-2)//2)で良いはず. +    return DP[(S, X)] -print((ans(N))) +print((ans(N, N)))