Count K-Reducible Numbers Less Than N

Count how many positive integers less than n (given as binary string s) reach 1 within at most k iterations of replacing a number by the count of its set bits. Key insight: the iteration depth depends only on the number of 1-bits, so the problem reduces to counting binary strings < s with specific Hamming weights (using combinatorics / digit DP) and summing those weights whose precomputed popcount-iteration length ≤ k (answer mod 1e9+7).