Estás en la posición \(s\) de una recta infinita y das exactamente \(k\) pasos, cada uno de una unidad a la izquierda o a la derecha. Cuenta cuántas secuencias de pasos te dejan en la posición \(e\). Dos secuencias son distintas si difieren en algún paso.

Entrada

La primera línea tiene \(T\) \((1 \le T \le 10^5)\). Cada una de las siguientes \(T\) líneas tiene \(s\), \(e\) y \(k\) \((|s|, |e| \le 2 \cdot 10^6, 1 \le k \le 10^6)\).

Salida

Para cada caso, una línea con la cantidad, módulo \(10^9 + 7\).

Ejemplo 1

Entrada

3
1 2 3
2 5 10
5 5 2

Salida

3
0
2