Count Numbers with the Same Set-Bit Count

You are given a positive integer n. Define f(n) as the smallest integer greater than or equal to n whose binary representation consists entirely of 1 bits.
Count the positive integers x that satisfy all of the following conditions:
x <= f(n)
x != n
x and n contain the same number of set bits in their binary representations
Return the count modulo 1,000,000,007.
Complete countSameBitNumbers for the given integer n.

Function
countSameBitNumbers(n: int) → int

Examples
Example 1
n = 6
return = 2
f(6) = 7, whose binary representation is 111. The integers other than 6 with two set bits and at most 7 are 3 (011) and 5 (101).
Example 2
n = 10
return = 5
f(10) = 15. Among the six four-bit patterns containing two set bits, one represents n itself, so five other integers qualify.
Example 3
n = 7
return = 0
The only positive integer at most 7 with three set bits is 7, which must be excluded.

Constraints
0 < n < 2^31

Let k be the bit length of n. f(n) is 2^k - 1, the smallest all-ones number at or above n. Every k-bit pattern with leading zeros allowed is then at most f(n), so the candidates are all k-bit patterns with the same popcount as n. That count is C(k, p), where p is popcount(n). Subtract 1 to exclude n itself, then take the result mod 1,000,000,007. Example 2 confirms it: k=4, p=2, C(4,2)=6, minus 1 gives 5. The pitfall is the edge case: when n is already all ones, like 7, C(k,k)=1 and the answer is 0. Also x must be positive, but with p>=1 the all-zero pattern is never counted. Don't iterate up to 2^31. Compute the binomial with Pascal's triangle up to 31 or with exact integers, then reduce mod. StealthCoder is there if the formula slips under pressure during the live assessment.

The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.