{"problem":{"name":"O. April Fools' Problem (hard)","description":{"content":"The plans for HC2 are rather far-fetched: we are just over 500 000 days away from HC2 3387, for example, and accordingly we are planning to have a couple hundred thousand problems in that edition (we ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":10000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF802O"},"statements":[{"statement_type":"Markdown","content":"The plans for HC2 are rather far-fetched: we are just over 500 000 days away from HC2 3387, for example, and accordingly we are planning to have a couple hundred thousand problems in that edition (we hope that programming contests will become wildly more popular). The marmots need to get to work, and they could use a good plan...\n\n## Input\n\nSame as the medium version, but the limits have changed: 1 ≤ _k_ ≤ _n_ ≤ 500 000.\n\n## Output\n\nSame as the medium version.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"HC#cf_span[2] 的计划相当遥远：例如，我们距离 HC#cf_span[2] 3387 还有 50 多万天，因此我们计划在该版本中准备几十万个问题（我们希望编程竞赛会变得异常流行）。土拨鼠们需要开始工作，它们需要一个良好的计划...\n\n与中等版本相同，但限制已更改：#cf_span[1 ≤ k ≤ n ≤ 500 000]。\n\n与中等版本相同。\n\n## Input\n\n与中等版本相同，但限制已更改：#cf_span[1 ≤ k ≤ n ≤ 500 000]。\n\n## Output\n\n与中等版本相同。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Given integers $ n $ and $ k $ such that $ 1 \\leq k \\leq n \\leq 500{,}000 $, compute the number of ways to choose $ k $ distinct elements from a set of $ n $ elements, modulo $ 10^9 + 7 $.\n\nThat is, compute $ \\binom{n}{k} \\mod (10^9 + 7) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF802O","tags":["binary search","data structures","flows"],"sample_group":[["8 4\n3 8 7 9 9 4 6 8\n2 5 9 4 3 8 9 1","32"]],"created_at":"2026-03-03 11:00:39"}}