Zadanie

Javor do súťaže

Počet bodov: 80

Je to tu. Jak každý rok. Jedinečná príležitosť presláviť sa po celom svete: súťaž KSP (Kráľovia Stromových Pestovateľov). Jednoznačne najlepší spôsob, ako svoj obchodík so záhradníckymi pomôckami presláviť na trhu. Janka o víťaztve snívala hádam už od… jedenástych narodenín. Jednosmerný lístok ku sláve jej rástol pod oknom jednoizbového bytu: Juhoplodný Jantárovolistý Javor, ktorý vypestovala, nemá na svete konkurencie.

Ježiši Mária! Jeleň jej ho obhrýzol. Jój, už vôbec nevyzerá tak pekne, ako mal.

Javí sa jediná možnosť - bude musieť strom obstrihať. Jedna vec je istá - nemôže to spraviť len tak ledabolo.

Jasné! Jabloň, ktorá minulý rok vyhrala súťaž, mala zaujímavý štýl, môžem ho napodobniť, pomyslela si. Jej pomocníci dorazili akonáhle si prečítali jej žiadosť o pomoc: junáci Jakub, Jozef a Jaroslav.

Javí sa však, že obstrihať strom na štýl minuloročnej jablone sa dá veľa spôsobmi, a kým sa na to Janka a jej pomocníci podujmú, chceli by vedieť, koľko majú možností.

Jasajte! Jednotlivec, ktorý toto musí zistiť, ste vy. Juchú!

Úloha

Janka má Juhoplodný Jantárovolistý Javor, inak povedané strom: graf, v ktorom sa z každého vrcholu dá dostať do každého iného práve jednou postupnosťou hrán. Tento strom je samozrejme zakorenený.

Potrebuje ho obstrihať tak, aby mal nasledovnú vlastnosť: ak sú vrcholy \(A\) a \(B\) rovnako hlboko v strome (rovnako vzdialené od koreňa), tak musí platiť, že \(A\) aj \(B\) majú rovnako veľa priamych potomkov.

Ešte si nieje istá, ako ho obstrihá, tak ju zaujíma, koľko rôznych stromov má na výber pre rôzne veľkosti (počty vrcholov).

Zrátajte, koľko stromov o \(n\) vrcholoch má vyššie popísanú vlastnosť.

Dva stromy považujeme za rovnaké, ak existuje bijekcia medzi ich vrcholmi (vieme prečíslovať vrcholy prvého stromu tak, aby podstromy každého vrcholu boli rovnaké ako v druhom strome).

Pre ujasnenie znázorníme všetky rôzne stromy s piatimi vrcholmi:

Keďže toto číslo môže byť obrovské, vypíšte tento počet modulo \(10^9 + 7\).

Vstup a Výstup

V prvom riadku je číslo \(1 \leq t \leq 1000\) - počet rôznych počtov vrcholov, ktoré Janka zvažuje.

V každom z nasledujúcich \(t\) riadkov je jedno číslo \(n\): počet vrcholov.

Pre každé \(n\) na vstupe vypíšte jedno číslo: koľko existuje stromov o \(n\) vrcholoch, kde rovnako hlboké vrcholy majú rovnako veľa priamych potomkov.

V prvej sade \(1 \leq n \leq 6\). V druhej sade \(1 \leq n \leq 40\). V tretej sade \(1 \leq n \leq 1000\). V štvrtej \(1 \leq n \leq 10^5\).

Príklad

Input:

3
1
2
5

Output:

1
1
5

Pre \(n = 1\) existuje jediný strom: sám koreň. Pre \(n = 2\) koreň s jedným potomkom. Pre \(n = 5\) sú možnosti znázornené v obrázku v zadaní.