{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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. "},{"iden":"output","content":"For 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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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$$","simple_statement":"Given N people, count how many ways to form a group of K or more people. Output the result modulo 1000000007.","has_page_source":false}