25006번 - Blocks 다국어

Sophie is playing with $n$ cuboid blocks. The $i$-th of her blocks has size $1 \times 1 \times i$.

Her favorite game is arranging all the blocks in parallel in a row in such a way that they all stand on their $1 \times 1$ faces (i.e., these are their bases). After arranging the blocks, Sophie stands at a large distance and watches the block arrangement from both ends of the row, which we shall refer to as the left end and the right end.  She walks so far away that each block obstructs visibility of all lower blocks behind it.  Sophie is satisfied if she sees exactly $\ell$ blocks from the left end and $p$ blocks from the right end.

She is wondering how many satisfying block arrangements exist. Help Sophie by writing a program that will: read the number of blocks and the numbers of blocks that she wants to see from the left and the right end, determines the number of satisfying arrangements, and prints the result to the standard output.

In the first line of input, there is the number of data sets $m$ ($1 \le m \le 100 \, 000$). Each of the $m$ lines that follow describes a single data set. Each description consists of three integers $n$, $\ell$, $p$ ($1 \le n \le 50 \, 000$, $1 \le \ell, p \le 100$), separated by single spaces. These specify the number of given blocks, the number of blocks Sophie wants to see from the left end, and the number of blocks she wants to see from the right end.

For each data set, your program should print a single line with only a single integer: the remainder modulo $10^9 + 7$ of the number of satisfying block arrangements.

In the first data set, Sophie is satisfied with the following block arrangements: $(1,2,4,3)$, $(1,3,4,2)$, $(2,3,4,1)$. In the $(1,2,4,3)$ arrangement, the blocks $1$, $2$, and $4$ are visible from the left, whereas $4$ and $3$ are visible from the right.