C - Contando caminos

Time limit: 4 seconds
Memory limit: 256 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

Fito quiere contar cuántos caminos puede formar saliendo del punto $(0,0)$ y terminando en el punto $(2N,0)$. Estos caminos no deben pasar nunca por debajo del eje $x$ y en cada movimiento se da un paso a la derecha y otro que puede ser arriba o abajo. Es decir, si se está en el punto $(x,y)$, los posibles puntos a los que se puede mover son $(x+1,y+1)$ ó $(x+1,y-1)$. Además de cumplir estas propiedades los caminos deben tener exactamente $R$ picos de altura $K$. Se le llama pico a un punto del camino donde el paso anterior fue de subida y el siguiente es de bajada.

Input

La primera línea de la entrada es un entero $T$ $(1 \leq T \leq 10)$ que indica la cantidad de casos de pruebas. Le siguen los $T$ casos, cada uno en una línea. Cada caso esta descrito por tres enteros $N$ $(1 \leq N \leq 100)$, $R$ $(0 \leq R \leq 100)$ y $K$ $(1 \leq K \leq 100)$ que representan respectivamente el tamaño de los caminos, la cantidad de picos y la altura que estos han de tener.

Output

Por cada caso de prueba se debe imprimir la cantidad de caminos que cumplen todas las propiedades mencionadas. Como este número puede ser muy grande se debe imprimir el resto de su división por $1000000007$.

Sample test(s)

Input
2 2 2 1 2 1 2
Output
1 1