The game of Mahjong originated in China and has become popular around the world. You do not need to have prior experience with Mahjong to solve this problem, and we will use different rules.

In our version of Mahjong, the player is given a set of $4K$0 tiles. Each tile has an integer rank written on it, and there are four identical copies of each rank from 1 to $K$. For example, for $K=5$, the set of tiles would be: 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5.

The player's goal is to select $M$ tiles from this set to form a winning hand. A winning hand consists of some number (possibly zero) of triples plus exactly one pair. A pair must consist of two tiles of the same rank. A triple can be either three tiles of the same rank (e.g., "2 2 2"), or three tiles with consecutive ranks (e.g., "3 4 5"). The ranks do not wrap around -- for example, "4 5 1" is not a valid triple.

Given $K$ and $M$, how many different winning hands are there? Two winning hands are considered the same if they use the same set of tiles, regardless of how those tiles are grouped to make triples and the pair. For instance, for $K=4$, $M=8$, the following two hands are considered the same:

"1 2 3, 1 2 3, 4 4"

"1 1, 2 3 4, 2 3 4"

The first line of the input gives the number of test cases, $T(1≤T≤100)$. $T$ lines follow. Each line contains two space-separated integers, $K(1≤K≤200)$ and $M(2≤M≤min(200,4K)$ and $M≡2(mod3))$.

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 winning hands, modulo $1000000007 (10^{9}+7)$.

4
1 2
3 5
4 5
9 14

Case #1: 1
Case #2: 9
Case #3: 20
Case #4: 13259

The 2015 China Collegiate Programming Contest