POLSKI SPOJ

Szymon jest bardzo pilnym uczniem. Zdobył już pięć tytułów laureata w przedmiotowych konkursach wiedzy z: biologi, chemii, fizyki, języka angielskiego oraz języka niemieckiego. Teraz zabrał się za informatykę. Podczas przeglądania zadań z poprzednich lat rzucił mu się w oczy jeden powtarzający się problem.

W zadaniu była plansza mająca n wierszy i m kolumn, był również Piotrek który stał w lewym dolnym rogu planszy i mógł wykonać 3 ruchy o jedno pole:

- w górę
- w prawo
- po przekątnej w prawą górną stronę

W zadaniu trzeba było podać liczbę różnych sposobów na które Piotrek może dojść do prawego górnego rogu planszy. Szymon oczywiście nie miał żadnego problemu z rozwiązaniem tego zadania. Ale zaczął się zastanawiać co by było gdyby Piotrek mógł się przesunąć o więcej niż jedno pole, mianowicie chodziło mu o to jaki byłby wynik gdyby Piotr mógł przesunąć się k pól lub mniej w danym kierunku. Oczywiście Piotr nie może się cofać ani stać w miejscu, więc w jednym ruchu musi się przesunąć przynajmniej o jedno pole (maksymalnie o k pól). Niestety to zadanie wydawało się dla Szymona za trudne a męczyło go po nocach tak jak rozpoczęte zadania ze SPOJ-a na których nie ma AC, więc poprosił Ciebie, starszego kolegę o pomoc!

Wejście

W pierwszym wierszu wejścia jedna liczba z ≤ 100 oznaczająca ilość zestawów danych. Następnie w z liniach liczby n, m oraz k 1 ≤ n,m,k ≤ 8000 oznaczające kolejno ilość wierszy i ilość kolumn po których może się poruszać Piotrek, a k oznacza maksymalną ilość pól o które może się przesunąć Piotrek w jednym z trzech kierunków podczas jednego ruchu.

Zawsze jest spełniony warunek max(n,m)*z ≤ 8000.

Wyjście

Na wyjściu z wierszy w każdym wierszu jedna liczba będącą odpowiedzią na pytanie: Na ile sposobów Piotrek może dojść do prawego górnego rogu planszy?

Liczba ta może być duża więc Szymon poprosił aby była podana modulo (10^9+103).

Przykład

Wejście:

2

3 4 2

3 5 3

Wyjście:

55

153