{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"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.\n\nIn our version of Mahjong, the player is given a set of $4K$ tiles. Each tile has an integer rank written on it, and there are four identical copies of each rank from $1$ to $K$.\nFor example, for $K \u003d 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`,\n`5`, `5`.\n\nThe player\u0027s 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.\nA 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\n(e.g., `3 4 5`). The ranks do not wrap around -- for example, `4 5 1` is not a valid triple.\n\nGiven $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\nmake triples and the pair. For instance, for $K \u003d 4$, $M \u003d 8$, the following two hands are considered the same:\n\n`1 2 3, 1 2 3, 4 4`\n\n`1 1, 2 3 4, 2 3 4`"}},{"title":"Input","value":{"format":"MD","content":"The first line of the input gives the number of test cases, $T$($1\\leq T\\leq 100$). $T$ lines follow. Each line contains two space-separated integers, $K$($1\\leq K\\leq 200$)\nand $M$($2\\leq M\\leq min(200, 4K)$ and $M \\equiv 2 \\pmod{3}$)."}},{"title":"Output","value":{"format":"MD","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 winning hands,\nmodulo $1000000007$ ($10^9 + 7$)."}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n1 2\n3 5\n4 5\n9 14\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 1\nCase #2: 9\nCase #3: 20\nCase #4: 13259\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"In `Case #1`, there are only four tiles -- `1`, `1`, `1`, `1` -- and the winning hand must consist of just a pair (with no triples).\nThere is only one possibility -- `1 1`. (Note that all the `1`s are interchangeable and it doesn\u0027t matter which two you pick.)\n\nIn `Case #2`, there are twelve tiles -- `1`, `1`, `1`, `1`, `2`, `2`, `2`, `2`, `3`, `3`, `3`, `3` -- and the winning hand must consist of one triple and one pair.\nThe nine possible hands are:\n\n```\n1 1 1, 2 2\n1 1 1, 3 3\n2 2 2, 1 1\n2 2 2, 3 3\n3 3 3, 1 1\n3 3 3, 2 2\n1 2 3, 1 1\n1 2 3, 2 2\n1 2 3, 3 3\n```\n\nNote that `3 3, 1 1 1` would not be considered a different hand from `1 1 1, 3 3` -- only the set of tiles matters, not how they are arranged."}}]}