{"problem":{"name":"C. Travelling Salesman and Special Numbers","description":{"content":"The Travelling Salesman spends a lot of time travelling so he tends to get bored. To pass time, he likes to perform operations on numbers. One such operation is to take a positive integer _x_ and redu","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF914C"},"statements":[{"statement_type":"Markdown","content":"The Travelling Salesman spends a lot of time travelling so he tends to get bored. To pass time, he likes to perform operations on numbers. One such operation is to take a positive integer _x_ and reduce it to the number of bits set to 1 in the binary representation of _x_. For example for number 13 it's true that 1310 = 11012, so it has 3 bits set and 13 will be reduced to 3 in one operation.\n\nHe calls a number _special_ if the minimum number of operations to reduce it to 1 is _k_.\n\nHe wants to find out how many special numbers exist which are not greater than _n_. Please help the Travelling Salesman, as he is about to reach his destination!\n\nSince the answer can be large, output it modulo 109 + 7.\n\n## Input\n\nThe first line contains integer _n_ (1 ≤ _n_ < 21000).\n\nThe second line contains integer _k_ (0 ≤ _k_ ≤ 1000).\n\nNote that _n_ is given in its binary representation without any leading zeros.\n\n## Output\n\nOutput a single integer — the number of special numbers not greater than _n_, modulo 109 + 7.\n\n[samples]\n\n## Note\n\nIn the first sample, the three special numbers are 3, 5 and 6. They get reduced to 2 in one operation (since there are two set bits in each of 3, 5 and 6) and then to 1 in one more operation (since there is only one set bit in 2).","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"旅行商花费大量时间旅行，因此容易感到无聊。为了打发时间，他喜欢对数字进行操作。其中一个操作是：取一个正整数 $x$，将其减少为 $x$ 的二进制表示中值为 $1$ 的位的个数。例如，对于数字 $13$，有 $13_{10} = 1101_2$，因此它有 $3$ 个置位，$13$ 在一次操作后将被减少为 $3$。\\n\\n他称一个数为 _特殊_ 的，如果将其减少到 $1$ 所需的最少操作次数为 $k$。\\n\\n他希望找出不超过 $n$ 的特殊数的个数。请帮助旅行商，因为他即将到达目的地！\\n\\n由于答案可能很大，请输出对 $10^9 + 7$ 取模的结果。\\n\\n第一行包含整数 $n$（$1 \\leq n < 2^{1000}$）。\\n\\n第二行包含整数 $k$（$0 \\leq k \\leq 1000$）。\\n\\n注意，$n$ 以二进制表示形式给出，且没有前导零。\\n\\n输出一个整数 —— 不超过 $n$ 的特殊数的个数，对 $10^9 + 7$ 取模。\\n\\n在第一个样例中，三个特殊数是 $3$、$5$ 和 $6$。它们在一次操作中被减少为 $2$（因为 $3$、$5$ 和 $6$ 的二进制表示中各有两个置位），然后在另一次操作中被减少为 $1$（因为 $2$ 的二进制表示中只有一个置位）。\"}, {\"iden\":\"input\",\"content\":\"第一行包含整数 $n$（$1 \\leq n < 2^{1000}$）。第二行包含整数 $k$（$0 \\leq k \\leq 1000$）。注意，$n$ 以二进制表示形式给出，且没有前导零。\"}, {\"iden\":\"output\",\"content\":\"输出一个整数 —— 不超过 $n$ 的特殊数的个数，对 $10^9 + 7$ 取模。\"}, {\"iden\":\"examples\",\"content\":\"输入1102输出3输入1111110112输出169\"}, {\"iden\":\"note\",\"content\":\"在第一个样例中，三个特殊数是 $3$、$5$ 和 $6$。它们在一次操作中被减少为 $2$（因为 $3$、$5$ 和 $6$ 的二进制表示中各有两个置位），然后在另一次操作中被减少为 $1$（因为 $2$ 的二进制表示中只有一个置位）。\"}]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ f(x) $ denote the number of 1-bits in the binary representation of $ x $, i.e., the population count (popcount).\n\nDefine $ g(x) $ as the minimum number of applications of $ f $ required to reduce $ x $ to 1:\n- $ g(1) = 0 $\n- For $ x > 1 $, $ g(x) = 1 + g(f(x)) $\n\nA number $ x $ is **special** if $ g(x) = k $.\n\nGiven:\n- $ n $: a positive integer given in binary string representation (without leading zeros), with $ 1 \\leq n < 2^{1000} $\n- $ k $: an integer, $ 0 \\leq k \\leq 1000 $\n\n**Objective:** Count the number of integers $ x \\in [1, n] $ such that $ g(x) = k $, modulo $ 10^9 + 7 $.\n\n---\n\n### Formal Statement:\n\nLet $ S = \\{ x \\in \\mathbb{Z}^+ \\mid 1 \\leq x \\leq n \\text{ and } g(x) = k \\} $\n\nCompute $ |S| \\mod (10^9 + 7) $\n\n---\n\n### Notes on $ g(x) $:\n\n- $ f(x) = \\text{popcount}(x) \\leq \\lfloor \\log_2 x \\rfloor + 1 $\n- Since $ f(x) < x $ for all $ x > 1 $, the sequence $ x, f(x), f(f(x)), \\dots $ strictly decreases until reaching 1.\n- Thus, $ g(x) $ is well-defined and finite for all $ x \\geq 1 $.\n- $ g(x) = k $ means that after exactly $ k $ applications of $ f $, we reach 1, and not earlier.\n\nLet $ h(m) = g(m) $. Then $ h $ can be precomputed for small values (since $ f(x) \\leq 1000 $ for $ x < 2^{1000} $, and $ f(x) $ reduces the value drastically).\n\nLet $ A_k = \\{ m \\in \\mathbb{Z}^+ \\mid g(m) = k \\} $\n\nWe are to count:  \n$$\n\\left| \\left\\{ x \\in [1, n] \\mid \\text{popcount}^{(k)}(x) = 1 \\text{ and } \\text{popcount}^{(k-1)}(x) > 1 \\right\\} \\right|\n$$\n\nEquivalently, use dynamic programming over the binary digits of $ n $, tracking:\n- Position in the binary string\n- Tight constraint (whether prefix equals prefix of $ n $)\n- Current popcount value (which is at most the number of bits so far, i.e., ≤ 1000)\n- The number of operations applied so far (i.e., how many times we have \"simulated\" $ f $, but we cannot simulate full $ g $ without knowing the entire number)\n\nBut note: we cannot compute $ g(x) $ for arbitrary $ x $ without knowing $ x $, and $ x $ can be up to $ 2^{1000} $.\n\nHowever, observe:\n\n- $ f(x) = \\text{popcount}(x) \\leq \\text{bit-length}(x) \\leq 1000 $\n- So $ f(x) \\in [1, 1000] $\n- Thus, $ g(x) = 1 + g(f(x)) $, and $ g $ only depends on the value of $ f(x) $, which is ≤ 1000.\n\nSo we can precompute $ g(m) $ for all $ m \\in [1, 1000] $.\n\nLet $ G[m] = g(m) $ for $ m = 1 $ to $ 1000 $\n\nThen, for any $ x \\leq n $, we have $ f(x) = \\text{popcount}(x) \\in [1, 1000] $, so:\n\n> $ g(x) = k $ if and only if $ G[\\text{popcount}(x)] = k - 1 $\n\nWait — correction:\n\nBy definition:\n- $ g(x) = 1 + g(f(x)) $\n- So $ g(x) = k \\iff g(f(x)) = k - 1 \\iff G[\\text{popcount}(x)] = k - 1 $\n\nThus:\n\n> $ x $ is special ⇔ $ G[\\text{popcount}(x)] = k - 1 $\n\nBut note: if $ k = 0 $, then $ g(x) = 0 \\Rightarrow x = 1 $\n\nSo:\n\n- If $ k = 0 $: count numbers $ x \\in [1, n] $ such that $ x = 1 $\n- If $ k \\geq 1 $: count numbers $ x \\in [1, n] $ such that $ \\text{popcount}(x) = m $, where $ G[m] = k - 1 $\n\nTherefore, define:\n\nLet $ T = \\{ m \\in [1, 1000] \\mid G[m] = k - 1 \\} $\n\nThen the answer is:\n$$\n\\sum_{m \\in T} \\left( \\text{number of integers } x \\in [1, n] \\text{ with } \\text{popcount}(x) = m \\right)\n$$\n\nBut note: if $ k = 1 $, then we require $ G[m] = 0 \\Rightarrow m = 1 $, so we count numbers with exactly one 1-bit — i.e., powers of two.\n\nIf $ k = 0 $, then we only count $ x = 1 $, provided $ 1 \\leq n $\n\nAlso, if $ T = \\emptyset $, then answer is 0.\n\nThus, the problem reduces to:\n\n> Given binary string $ n $, and a set $ T \\subseteq [1, 1000] $, count the number of integers $ x \\in [1, n] $ such that the number of 1-bits in $ x $ is in $ T $.\n\nThis is a classic digit DP problem.\n\n---\n\n### Final Formal Statement:\n\nLet $ n $ be a binary string of length $ L \\leq 1000 $, representing an integer $ N $.\n\nLet $ G: [1, 1000] \\to \\mathbb{N} $ be defined recursively:\n- $ G(1) = 0 $\n- For $ m > 1 $, $ G(m) = 1 + G(\\text{popcount}(m)) $\n\nLet $ T = \\{ m \\in [1, 1000] \\mid G(m) = k - 1 \\} $\n\nIf $ k = 0 $, then $ T = \\{1\\} $ if $ k = 0 $, but wait — correction:\n\nActually:\n\n- $ g(x) = 0 \\iff x = 1 $ → so for $ k = 0 $, we want $ x = 1 $\n- For $ k \\geq 1 $, $ g(x) = k \\iff g(f(x)) = k - 1 \\iff G(\\text{popcount}(x)) = k - 1 $\n\nSo define:\n\n- If $ k = 0 $: answer = 1 if $ n \\geq 1 $, else 0 → but $ n \\geq 1 $ always, so answer = 1 if $ 1 \\leq n $, which it is.\n- But wait: what if $ k = 0 $ and $ n = 1 $? Then only $ x = 1 $, so 1 number.\n- What if $ k = 0 $ and $ n > 1 $? Still only $ x = 1 $ qualifies → answer = 1.\n\nBut what if $ k = 0 $ and $ n = 0 $? But $ n \\geq 1 $ per input.\n\nSo:\n\n- If $ k = 0 $: answer = 1 (since $ x = 1 $ is always ≤ $ n $, and $ n \\geq 1 $)\n- If $ k \\geq 1 $: let $ T = \\{ m \\in [1, 1000] \\mid G(m) = k - 1 \\} $, and compute\n  $$\n  \\sum_{m \\in T} \\text{count}(m)\n  $$\n  where $ \\text{count}(m) $ = number of integers $ x \\in [1, n] $ with exactly $ m $ bits set to 1.\n\nBut note: $ x = 0 $ is not allowed (positive integers), and $ \\text{popcount}(x) \\geq 1 $, so we are safe.\n\nAlso, if $ m > L $, then $ \\text{count}(m) = 0 $, since $ n $ has $ L $ bits, so no number ≤ $ n $ can have more than $ L $ bits set.\n\nSo we can compute $ \\text{count}(m) $ for $ m = 1 $ to $ \\min(L, 1000) $ using digit DP.\n\n---\n\n### Final Answer Formulation:\n\nLet $ L = \\text{len}(n) $, where $ n $ is given as a binary string.\n\nPrecompute $ G[1..1000] $:\n- $ G[1] = 0 $\n- For $ i = 2 $ to $ 1000 $: $ G[i] = 1 + G[\\text{popcount}(i)] $\n\nLet $ T = \\begin{cases}\n\\{1\\} & \\text{if } k = 0 \\\\\n\\{ m \\in [1, 1000] \\mid G[m] = k - 1 \\} & \\text{if } k \\geq 1\n\\end{cases} $\n\nDefine $ \\text{dp}[i][tight][ones] $: number of ways to fill the first $ i $ bits of $ n $, with tight constraint, and having accumulated $ ones $ 1-bits.\n\nThen compute:\n$$\n\\text{ans} = \\sum_{m \\in T} \\text{dp}[L][0][m] + \\text{dp}[L][1][m]\n$$\n\nBut note: we must exclude $ x = 0 $. Since we start from the first bit and require at least one 1, and $ n \\geq 1 $, we are counting only $ x \\in [1, n] $.\n\nActually, standard digit DP for numbers from 1 to $ n $ can be implemented by counting numbers from 0 to $ n $, then subtracting the count for 0 (which is 1 if 0 is included). But since we are counting numbers with exactly $ m \\geq 1 $ bits set, 0 has 0 bits and won't be counted. So we can do DP from 0 to $ n $, and it's fine.\n\nBut to be safe: we can design DP to count numbers in $ [0, n] $ with popcount in $ T $, then subtract 1 if $ 0 \\in T $ — but $ T \\subseteq [1,1000] $, so 0 is never in $ T $. So we are safe.\n\nThus:\n\n> Compute $ C = \\sum_{m \\in T} \\text{count}_{\\leq n}(m) $, where $ \\text{count}_{\\leq n}(m) $ = number of integers $ x \\in [0, n] $ with exactly $ m $ bits set.\n\nThen output $ C \\mod (10^9 + 7) $\n\nBut note: if $ k = 0 $, then $ T = \\{1\\} $, but we want $ x = 1 $, which has popcount 1. So this matches.\n\nWait — if $ k = 0 $, then $ g(x) = 0 \\iff x = 1 $, so we want numbers with $ g(x) = 0 $, which is only $ x = 1 $, which has popcount 1.\n\nSo yes, $ T = \\{ m \\mid G(m) = -1 \\} $? No.\n\nWait — correction:\n\nWe defined:\n- $ g(x) = k \\iff G[\\text{popcount}(x)] = k - 1 $\n\nSo for $ k = 0 $: $ G[\\text{popcount}(x)] = -1 $ → impossible.\n\nMistake here.\n\nLet’s re-derive carefully.\n\nDefine:\n- $ g(1) = 0 $\n- $ g(x) = 1 + g(f(x)) $ for $ x > 1 $\n\nSo:\n- $ g(x) = 0 \\iff x = 1 $\n- $ g(x) = 1 \\iff f(x) = 1 \\iff \\text{popcount}(x) = 1 $\n- $ g(x) = 2 \\iff f(x) \\in \\{2,3\\} $ because $ g(2) = g(3) = 1 $, since $ f(2) = f(3) = 1 \\Rightarrow g(2) = g(3) = 1 $\n\nSo:\n- $ g(x) = k \\iff g(f(x)) = k - 1 $\n\nSo for $ k \\geq 1 $: $ g(x) = k \\iff G[\\text{popcount}(x)] = k - 1 $\n\nBut for $ k = 0 $: $ g(x) = 0 \\iff x = 1 $\n\nSo we must handle $ k = 0 $ separately.\n\nThus:\n\n- If $ k = 0 $: answer = 1 if $ n \\geq 1 $, else 0 → always 1 (since $ n \\geq 1 $)\n- If $ k \\geq 1 $: answer = number of $ x \\in [1, n] $ such that $ \\text{popcount}(x) \\in T $, where $ T = \\{ m \\in [1, 1000] \\mid G(m) = k - 1 \\} $\n\nSo final formulation:\n\n---\n\nLet $ G[1] = 0 $\n\nFor $ m = 2 $ to $ 1000 $:  \n$ G[m] = 1 + G[\\text{popcount}(m)] $\n\nLet $ T = \\begin{cases}\n\\emptyset & \\text{if } k = 0 \\text{ (handled separately)} \\\\\n\\{ m \\in [1, 1000] \\mid G[m] = k - 1 \\} & \\text{if } k \\geq 1\n\\end{cases} $\n\nThen:\n\n$$\n\\text{Answer} =\n\\begin{cases}\n1 & \\text{if } k = 0 \\\\\n\\sum_{m \\in T} \\left( \\text{number of integers } x \\in [1, n] \\text{ with } \\text{popcount}(x) = m \\right) & \\text{if } k \\geq 1\n\\end{cases}\n\\mod (10^9 + 7)\n$$\n\nAnd the count for each $ m $ is computed via digit DP on binary string $ n $.\n\n--- \n\n**Note**: Since $ n < 2^{1000} $, its binary representation has at most 1000 bits. We can do DP with state:  \n$ dp[pos][tight][ones] $, where  \n- $ pos \\in [0, L] $  \n- $ tight \\in \\{0,1\\} $  \n- $ ones \\in [0, 1000] $\n\nTotal states: $ 1000 \\times 2 \\times 1001 \\approx 2 \\times 10^6 $, feasible.\n\nWe precompute $ G[1..1000] $ in $ O(1000 \\cdot \\log 1000) $, trivial.\n\nWe then compute the digit DP.\n\nFinal output: answer mod $ 10^9 + 7 $\n\n--- \n\n### Final Answer (Formal Mathematical Statement):\n\nLet $ n \\in \\mathbb{N} $ be given in binary representation as a string of length $ L \\leq 1000 $, with $ n \\geq 1 $.\n\nDefine $ f(x) = \\text{popcount}(x) $, and recursively define $ g: \\mathbb{N}^+ \\to \\mathbb{N} $ by:\n$$\ng(x) =\n\\begin{cases}\n0 & \\text{if } x = 1 \\\\\n1 + g(f(x)) & \\text{if } x > 1\n\\end{cases}\n$$\n\nLet $ k \\in \\mathbb{N} $, $ 0 \\leq k \\leq 1000 $.\n\nDefine the set:\n$$\nS_k = \\{ x \\in \\mathbb{N}^+ \\mid x \\leq n \\text{ and } g(x) = k \\}\n$$\n\nCompute $ |S_k| \\mod (10^9 + 7) $.\n\n---\n\n**Note**: The problem reduces to counting numbers $ \\leq n $ with popcount in a precomputed set $ T $, with $ T $ derived from $ G = g|_{[1,1000]} $, and handling $ k = 0 $ as a special case.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF914C","tags":["brute force","combinatorics","dp"],"sample_group":[["110\n2","3"],["111111011\n2","169"]],"created_at":"2026-03-03 11:00:39"}}