P2 - Poukážky 2

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Dňa 14.6.2022 sa uskutoční finálové kolo súťaže Palma. Pre najlepšie tímy sú pripravené ako ceny poukážky na nákup v jednom nemenovanom obchode.
Univerzita nakúpila poukážky na viacero súťaží naraz, takže pre Palmu dostanú jej organizátori P poukážok, všetky v rovnakej hodnote. Neľahkou úlohou je rozdeliť všetky poukážky medzi prvých T tímov. Samozrejme, tím umiestnený vyššie musí dostať aspoň toľko poukážok ako tím umiestnený nižšie vo výsledkovej listine. Organizátori prihliadajú aj na počet žiakov v tímoch. Ten bude ale známy až po skončení druhého finálového kola, pomôžte im zatiaľ spočítať možnosti rozdelenia poukážok medzi tímy bez zohľadnenia počtu žiakov.

Úloha

Pre dané čísla T a P zistite počet možných rozdelení poukážok.

Vstup

V prvom riadku súboru sa nachádza číslo Q udávajúce počet sád.

Nasleduje Q riadkov s dvojicou čísel T a P.

P1

1 ≤ Q ≤ 100
1 ≤ T ≤ 6
1 ≤ P ≤ 10

P2

1 ≤ Q ≤ 1 000
1 ≤ T ≤ 100
1 ≤ P ≤ 5 000

Výstup

Výstupom programu je výsledok pre každú sadu modulo 2³⁰-1 na samostatnom riadku.

Príklad

Vstup:

Výstup:

1
3
10

20 Finále