406711: GYM102503 H A Sheety Problem

Miguel used to pack sopas, and pack pasta. He realized that he wasn't satisfied with his packing job. So he looked deep inside himself, and remembered how his mother used to pack sheets. This was inspiration for him to become a CloudSound wrapper.

CloudSound is a rapidly growing groceries startup. Their idea is to take substandard vegetables that supermarkets wouldn't sell, and deliver them directly to consumers at marked down prices. Miguel works in the root crop packaging division. In particular, his job involves wrapping sick beets in sheets.

Abra also works in CloudSound, and his job involves bringing stacks of sheets to other CloudSound wrappers to use for packaging. To help save the environment, CloudSound uses recycled documents from businesses, which were thrown away due to misprints.

Today, Abra brought Miguel a stack of $$$n$$$ sheets, which originally came from $$$2n$$$ pages of what was supposed to be a religious document. Because of a misprint, the first sheet has page $$$1$$$ printed on the front and page $$$2$$$ printed at the back. The second sheet has page $$$2$$$ printed on the front and page $$$3$$$ printed at the back. And in general, the $$$i$$$th sheet has page $$$i$$$ printed on the front and $$$i+1$$$ printed on the back. As Miguel was cleaning up for the day, however, he bumped into Abra and dropped the stack of sheets. In other words, Miguel messed up while he packed up.

Abra put the $$$n$$$ sheets in a stack which is now disorganized. But then Miguel noticed something divine. Consider two sheets $$$s$$$ and $$$t$$$ such that $$$s$$$ is closer to the top of the disorganized stack than $$$t$$$. If both page numbers of $$$s$$$ are larger than both page numbers of $$$t$$$, Miguel considers this a divine pair of holy packing sheets.

Miguel counts $$$k$$$ different pairs of holy packing sheets in Abra's stack. Now Abra asks: How many ways are there to arrange the $$$n$$$ sheets such that there are exactly $$$k$$$ different pairs of holy packing sheets? Help our two CloudSound wrappers collaborate by answering this question. Note that we ignore the orientation of the sheets in the stack, so there are exactly $$$n!$$$ arrangements in total. In other words, we don't give a sheet about the orientation.

The first line of input contains $$$t$$$, the number of test cases.

Each test case consists of a single line containing two space-separated integers $$$n$$$ and $$$k$$$, the number of sheets and the number of pairs of holy packing sheets.

For each test case, print a single line containing the number of ways to arrange the $$$n$$$ sheets such that there are $$$k$$$ pairs of holy packing sheets. Since the answer can be very large, print the answer modulo $$$987654321$$$.

$$$1 \le t \le 10^5$$$

$$$0 \le n, k \le 750$$$

Subtask 1 (15 points): $$$n \le 5$$$

Subtask 2 (20 points): $$$n \le 8$$$

Subtask 3 (15 points): $$$n \le 16$$$

Subtask 4 (24 points): $$$n \le 24$$$

Subtask 5 (11 points): $$$n \le 50$$$

Subtask 6 (7 points): $$$n \le 100$$$

Subtask 7 (8 points): No additional constraints.

1
4 2

7

Recall that due to the misprint, the 1st sheet has pages 1 and 2, the 2nd sheet has pages 2 and 3, the 3rd sheet has pages 3 and 4, while the 4th sheet has pages 4 and 5.

One possible way to arrange them such that there are exactly 2 different divine pairs of holy packing sheets is in the order $$$3, 2, 4, 1$$$, where $$$3$$$ is on top of the stack and $$$1$$$ is at the bottom. Note that $$$3$$$ and $$$1$$$ form a divine pair of holy packing sheets because both pages $$$3$$$ and $$$4$$$ are greater than pages $$$1$$$ and $$$2$$$. Similarly, $$$4$$$ and $$$1$$$ form the other divine pair of holy packing sheets because pages $$$4$$$ and $$$5$$$ are both greater than pages $$$1$$$ and $$$2$$$.

Note also that in this arrangement, $$$3$$$ and $$$2$$$ do not form a divine pair of holy packing sheets because the page 3 on the 3rd sheet is not greater than the page 3 on the 2nd sheet. Also, $$$2$$$ and $$$4$$$ do not form a divine pair of holy packing sheets because $$$2$$$ is the one that is closer to the top of the stack than $$$4$$$ is.

Using this same notation, the 7 total arrangements are,

• 2 3 4 1
• 2 4 3 1
• 3 2 4 1
• 3 1 4 2
• 4 1 2 3
• 4 2 1 3
• 4 1 3 2