import time


def timer(func):
    def wrapper(*args, **kwargs):
        start_time = time.time()
        result = func(*args, **kwargs)
        end_time = time.time()
        elapsed_time = end_time - start_time
        print(f"{func.__name__} time: {elapsed_time:.6f} seconds")
        return result

    return wrapper


@timer
def count_combinations_above_million(limit_n=100, threshold=1_000_000):
    """
    对于 1 ≤ n ≤ limit_n，统计组合数 C(n, r) 大于 threshold 的个数。
    利用递推 C(n, r) = C(n, r-1) * (n - r + 1) / r 以及对称性 C(n, r) = C(n, n-r)。
    """
    count = 0

    for n in range(1, limit_n + 1):
        comb = 1  # C(n, 0)
        # 只需检查 r 从 1 到 n//2
        for r in range(1, n // 2 + 1):
            # 递推更新组合数
            comb = comb * (n - r + 1) // r

            if comb > threshold:
                # 一旦找到最小的 r 使得 C(n, r) > threshold，
                # 则 r 到 n-r 之间的所有值都满足条件。
                # 符合条件的个数 = (n - r) - r + 1 = n - 2*r + 1
                count += n - 2 * r + 1
                break  # 该 n 的剩余情况不必再检查

    return count


if __name__ == "__main__":
    result = count_combinations_above_million()
    print(result)