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