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>).
from itertools import combinations as comb

def cp(Set):
    return [(a,b) for a in Set for b in Set]

def boolean(Set):
    size = 2**len(Set)
    res = [[] for i in range(size)]
    for i in range(size):
        for j in range(len(Set)):
            if i & (1<<j):
                res[i].append(Set[j])
    return res[1:]

def perfSet(Set):
    l = cp(Set)
    for (a,b) in l:
        if a ^ b not in Set:
            return False
    return True

n = int(input())
Set = list(range(n+1))
Sets = boolean(Set)
count = 0

for x in Sets:
    if perfSet(x) == True:
        count += 1

print(count)
