{"problem":{"name":"M. Chat Group","description":{"content":"It is said that a dormitory with 6 persons has 7 chat groups _^_^_. But the number can be even larger: since every 3 or more persons could make a chat group, there can be 42 different chat groups. Gi","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10177M"},"statements":[{"statement_type":"Markdown","content":"It is said that a dormitory with 6 persons has 7 chat groups _^_^_. But the number can be even larger: since every 3 or more persons could make a chat group, there can be 42 different chat groups.\n\nGiven N persons in a dormitory, and every K or more persons could make a chat group, how many different chat groups could there be?\n\nThe input starts with one line containing exactly one integer T which is the number of test cases.\n\nEach test case contains one line with two integers N and K indicating the number of persons in a dormitory and the minimum number of persons that could make a chat group.\n\nFor each test case, output one line containing \"_Case #x: y_\" where _x_ is the test case number (starting from 1) and _y_ is the number of different chat groups modulo 1000000007.\n\n## Input\n\nThe input starts with one line containing exactly one integer T which is the number of test cases.Each test case contains one line with two integers N and K indicating the number of persons in a dormitory and the minimum number of persons that could make a chat group.  1 ≤ T ≤ 100.  1 ≤ N ≤ 109.  3 ≤ K ≤ 105. \n\n## Output\n\nFor each test case, output one line containing \"_Case #x: y_\" where _x_ is the test case number (starting from 1) and _y_ is the number of different chat groups modulo 1000000007.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ i \\in \\{1, \\dots, T\\} $, let $ N_i \\in \\mathbb{Z} $ be the number of persons, and $ K_i \\in \\mathbb{Z} $ be the minimum group size.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 1000 $  \n2. For each test case: $ 1 \\leq K_i \\leq N_i \\leq 10^9 $\n\n**Objective**  \nFor each test case $ i $, compute the number of subsets of size at least $ K_i $ from $ N_i $ persons:  \n$$\ny_i = \\sum_{j=K_i}^{N_i} \\binom{N_i}{j} \\mod 1000000007\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10177M","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}