8816번 - Klasa 다국어

문제

W klasie Hektora uczy się N osób i N jest parzyste. Hektor zastanawia się kto z kim będzie siedział w ławce w nadchodzącym roku szkolnym.

Na ile różnych sposobów uczniowie mogą dobrać się w pary?

Dwa sposoby uznajemy za różne jeśli co najmniej jeden uczeń w pierwszym sposobie był w parze z kimś innym niż w drugim.

입력

W pierwsze linii znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10). Następnie podawane są opisy kolejnych zestawów.

W pierwszej linii zestawu znajduje się liczba naturalna N ( 2 <= N <= 1000000, N parzyste ) oznaczająca liczbę uczniów w klasie.

출력

Dla każdego zestawu należy obliczyć liczbę różnych sposobów dobrania uczniów w pary. Ponieważ ta liczba może być bardzo duża należy wypisać jej resztę z dzielenia przez 1000.

제한

힌트