class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:
        @cache
        def dfs(pos, limit, cnt):
            if pos == 0:
                return cnt
            res = 0
            up = (self.num >> (pos - 1) & 1) if limit else 1
            for i in range(up + 1):
                res += dfs(pos - 1, limit and i == up, cnt + (i == 1 and pos % x == 0))
            return res

        l, r = 1, 10**18
        while l < r:
            mid = (l + r + 1) >> 1
            self.num = mid
            v = dfs(mid.bit_length(), True, 0)
            dfs.cache_clear()
            if v <= k:
                l = mid
            else:
                r = mid - 1
        return l