405067: GYM101775 A Chat Group

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.

Given N persons in a dormitory, and every K or more persons could make a chat group, how many different chat groups could there be?

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 ≤ 10⁹.
• 3 ≤ K ≤ 10⁵.

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.

1
6 3

Case #1: 42