{"raw_statement":[{"iden":"statement","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..."},{"iden":"input","content":"Same as the medium version, but the limits have changed: 1 ≤ _k_ ≤ _n_ ≤ 500 000."},{"iden":"output","content":"Same as the medium version."},{"iden":"example","content":"Input\n\n8 4\n3 8 7 9 9 4 6 8\n2 5 9 4 3 8 9 1\n\nOutput\n\n32"}],"translated_statement":[{"iden":"statement","content":"HC#cf_span[2] 的计划相当遥远：例如，我们距离 HC#cf_span[2] 3387 还有 50 多万天，因此我们计划在该版本中准备几十万个问题（我们希望编程竞赛会变得异常流行）。土拨鼠们需要开始工作，它们需要一个良好的计划...\n\n与中等版本相同，但限制已更改：#cf_span[1 ≤ k ≤ n ≤ 500 000]。\n\n与中等版本相同。\n\n"},{"iden":"input","content":"与中等版本相同，但限制已更改：#cf_span[1 ≤ k ≤ n ≤ 500 000]。"},{"iden":"output","content":"与中等版本相同。"}],"sample_group":[],"show_order":[],"formal_statement":"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) $.","simple_statement":null,"has_page_source":false}