시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6 6 5 100.000%

문제

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.

예제 입력 1

4
2
4
6
12

예제 출력 1

1
3
15
395

출처

Contest > Spot > HotSpot 2010 1-2번