Təsadüfi Gəzintilər#6575
"Thorfun Company Limited" və ya "thorfun.com", bloggerlər, yazıçılar və oxucular üçün bir sosial şəbəkədir və dörd yeni məzun tərəfindən təsis edilmişdir. Onlardan biri hesablama problemlərinə böyük maraq göstərir. Bir gün o, çox maraqlı bir problem tapdı: "Təsadüfi Gəzintilər". Bu problem bir çox fərqli məsələnin həllini əhatə edir. Sizə bir ölçülü xətt verilir və başlanğıc nöqtəsində (mövqe 0) dayanırsınız. Hər addımda ya sola, ya da sağa bir vahid uzunluqda hərəkət edə bilərsiniz.
Əvvəlcə problemin əsas versiyasına baxaq. Siz 2N addım ataraq istədiyiniz kimi hərəkət edə bilərsiniz, lakin başlanğıc nöqtəsində bitməlisiniz. Neçə fərqli yolla hərəkət edə bilərsiniz? Həll çox sadədir. Eyni nöqtədə başlayıb bitdiyiniz üçün eyni sayda sol və sağ addım atmalısınız. 2N addımdan N sağ və N sol addım seçmək lazımdır.
"Təsadüfi Gəzintilər" problemi əsas problemə bənzəyir, lakin bir fərqlə: gəzintilər zamanı mənfi tam ədədlərə daxil olmamalısınız. Məsələn, əgər N = 1 olarsa, 0→1→0 yolunda hərəkət edə bilərsiniz, lakin 0→-1→0 yolunda hərəkət edə bilməzsiniz. Sizin vəzifəniz, yuxarıdakı qaydalara uyğun gələn yolların sayını hesablamaq üçün bir proqram yazmaqdır. Nəticə çox böyük ola bilər, buna görə də nəticəni 1000000007 (əsas ədəd) ilə modulyasiya edərək çap edin.
Girişin ilk sətri test halların sayı T ≤ 1000 olan bir rəqəmdir.
Hər bir test halı bir tam ədəd N (1 ≤ N ≤ 1000000) olan bir sətrdən ibarətdir.
Hər bir test halı üçün, 1000000007 ilə modulyasiya edilmiş gəzə biləcəyiniz yolların sayını göstərən bir tam ədəd göstərin.
Nümunə 1