import bisect
from itertools import combinations
 
class UserMainCode(object):
    @staticmethod
    def FindSurprisingNumbersSum(input1):
        MOD = 1000000007
 
        # Function to generate all numbers with exactly 3 set bits using combinations
        def generate_surprising_numbers():
            surprising_numbers = []
            for combo in combinations(range(32), 3):  # Generate all combinations of 3 bits
                number = (1 << combo[0]) + (1 << combo[1]) + (1 << combo[2])
                surprising_numbers.append(number)
            surprising_numbers.sort()  # Sort the numbers
            return surprising_numbers
 
        # Generate surprising numbers
        surprising_numbers = generate_surprising_numbers()
 
        # Precompute the prefix sum of surprising numbers
        prefix_sum = [0] * (len(surprising_numbers) + 1)
        for i in range(1, len(surprising_numbers) + 1):
            prefix_sum[i] = (prefix_sum[i - 1] + surprising_numbers[i - 1]) % MOD
 
        # Find the largest surprising number <= input1 using binary search
        idx = bisect.bisect_right(surprising_numbers, input1)
 
        # The sum of surprising numbers up to the found index
        return prefix_sum[idx] % MOD# your code goes here

aW1wb3J0IGJpc2VjdApmcm9tIGl0ZXJ0b29scyBpbXBvcnQgY29tYmluYXRpb25zCgpjbGFzcyBVc2VyTWFpbkNvZGUob2JqZWN0KToKICAgIEBzdGF0aWNtZXRob2QKICAgIGRlZiBGaW5kU3VycHJpc2luZ051bWJlcnNTdW0oaW5wdXQxKToKICAgICAgICBNT0QgPSAxMDAwMDAwMDA3CiAgICAgICAgCiAgICAgICAgIyBGdW5jdGlvbiB0byBnZW5lcmF0ZSBhbGwgbnVtYmVycyB3aXRoIGV4YWN0bHkgMyBzZXQgYml0cyB1c2luZyBjb21iaW5hdGlvbnMKICAgICAgICBkZWYgZ2VuZXJhdGVfc3VycHJpc2luZ19udW1iZXJzKCk6CiAgICAgICAgICAgIHN1cnByaXNpbmdfbnVtYmVycyA9IFtdCiAgICAgICAgICAgIGZvciBjb21ibyBpbiBjb21iaW5hdGlvbnMocmFuZ2UoMzIpLCAzKTogICMgR2VuZXJhdGUgYWxsIGNvbWJpbmF0aW9ucyBvZiAzIGJpdHMKICAgICAgICAgICAgICAgIG51bWJlciA9ICgxIDw8IGNvbWJvWzBdKSArICgxIDw8IGNvbWJvWzFdKSArICgxIDw8IGNvbWJvWzJdKQogICAgICAgICAgICAgICAgc3VycHJpc2luZ19udW1iZXJzLmFwcGVuZChudW1iZXIpCiAgICAgICAgICAgIHN1cnByaXNpbmdfbnVtYmVycy5zb3J0KCkgICMgU29ydCB0aGUgbnVtYmVycwogICAgICAgICAgICByZXR1cm4gc3VycHJpc2luZ19udW1iZXJzCgogICAgICAgICMgR2VuZXJhdGUgc3VycHJpc2luZyBudW1iZXJzCiAgICAgICAgc3VycHJpc2luZ19udW1iZXJzID0gZ2VuZXJhdGVfc3VycHJpc2luZ19udW1iZXJzKCkKCiAgICAgICAgIyBQcmVjb21wdXRlIHRoZSBwcmVmaXggc3VtIG9mIHN1cnByaXNpbmcgbnVtYmVycwogICAgICAgIHByZWZpeF9zdW0gPSBbMF0gKiAobGVuKHN1cnByaXNpbmdfbnVtYmVycykgKyAxKQogICAgICAgIGZvciBpIGluIHJhbmdlKDEsIGxlbihzdXJwcmlzaW5nX251bWJlcnMpICsgMSk6CiAgICAgICAgICAgIHByZWZpeF9zdW1baV0gPSAocHJlZml4X3N1bVtpIC0gMV0gKyBzdXJwcmlzaW5nX251bWJlcnNbaSAtIDFdKSAlIE1PRAogICAgICAgIAogICAgICAgICMgRmluZCB0aGUgbGFyZ2VzdCBzdXJwcmlzaW5nIG51bWJlciA8PSBpbnB1dDEgdXNpbmcgYmluYXJ5IHNlYXJjaAogICAgICAgIGlkeCA9IGJpc2VjdC5iaXNlY3RfcmlnaHQoc3VycHJpc2luZ19udW1iZXJzLCBpbnB1dDEpCiAgICAgICAgCiAgICAgICAgIyBUaGUgc3VtIG9mIHN1cnByaXNpbmcgbnVtYmVycyB1cCB0byB0aGUgZm91bmQgaW5kZXgKICAgICAgICByZXR1cm4gcHJlZml4X3N1bVtpZHhdICUgTU9EIyB5b3VyIGNvZGUgZ29lcyBoZXJl