Prihlásenie Registrácia  

D - Súčet

Č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 ]

Mário sa dnes na informatike učil rekurziu a má za úlohu vypísať všetky možné unikátne zápisy daného čísla vo forme súčtu.
Samozrejme svoj výtvor najprv pustil na nehorázne veľkom vstupe a program mu padol. Namiesto voľby menšieho čísla sa rozhodol vniesť do úlohy ďalšie obmedzenie a tak si ju zjednodušiť.
Najprv by ale rád vedel, či je to naozaj až tak dobrý nápad, veď ako by mu malo pomôcť to, že súčet obmedzí len na N čisel.
Pomôžte mu zistiť, koľkými spôsobmi sa dá zapísať S ako súčet N prirodzených čísel

Úloha

Pre dané čísla N a S zistite počet unikátnych N-prvkových postupností (ignorujuc permutacie) prirodzených čísel (Z+∪{0}) so súčtom S

Vstup

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

Nasleduje Q riadkov s dvojicou čísel N a S.
1 ≤ Q ≤ 1 000

1 ≤ N ≤ 100
1 ≤ S ≤ 5000

Výstup

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

Príklad

Vstup:

2
1 100
3 8

Výstup:

1
10