Fox Ciel studies number theory.

She thinks a non-empty set *S* contains non-negative integers is perfect if and only if for any <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/9ef9929d40fa162bdd76a55da469dde6fc13a5f5.png" style="max-width: 100.0%;max-height: 100.0%;"/> (*a* can be equal to *b*), <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/bba2b10c821617f53f33d4f198ad3dfee0eb6ecd.png" style="max-width: 100.0%;max-height: 100.0%;"/>. Where operation *xor* means exclusive or operation (http://en.wikipedia.org/wiki/Exclusive_or).

Please calculate the number of perfect sets consisting of integers not greater than *k*. The answer can be very large, so print it modulo 1000000007 (10<sup class="upper-index">9</sup> + 7).
The first line contains an integer *k* (0 ≤ *k* ≤ 10<sup class="upper-index">9</sup>).
mod = 10 ** 9 + 7
ans = 0

n = int(input()) + 1

ans += n

a = []
while n > 0:
    if n % 2 == 1:
        a.append(1)
    else:
        a.append(0)
    n //= 2

tail = [0]
for i in range(len(a)):
    tail.append(tail[-1] + 2 ** i * a[i])


d = [[0 for i in range(len(a))] for j in range(len(a))]
h = [[0 for i in range(len(a))] for j in range(len(a))]

prev = 0
for i in range(len(a) - 1, -1, -1):
    prev += a[i]
    if a[i] == 1:
        h[i][prev - 1] += 1
        if prev >= 2:
            ans += (2 ** (i * (prev - 1))) * tail[i]
            ans %= mod

for i in range(len(a) - 1, -1, -1):
    if i == len(a) - 1:
        continue
    for j in range(0, len(a)):
        # print("dump i = {0}, j = {1}".format(i, j))
        h[i][j] += h[i + 1][j]
        if j > 0:
            h[i][j] += h[i + 1][j - 1]
            d[i][j] = h[i + 1][j - 1]
        d[i][j] %= mod
        h[i][j] %= mod

        if j >= 2:
            ans += (2 ** (i * j)) * d[i][j]
            ans %= mod

print(ans)


