Ako sa tak blíži čas jesenného sústredenia, treba začať hľadať chatu. Keďže však KSP všetky financie od sponzorov drží v kryptomenách, nič luxusné si nemôže dovoliť. “Zvýšme účastnícky poplatok na 150 eur!”, navrhol Dávid. “Tak to vôbec! Kde si také niečo videl? To radšej ušetríme na záchodoch…”, rozhorčuje sa Emma vymýšľajúc ako z nedostatku toaliet spraviť zábavu. “Hmmm, len aby to nebolo nespravodlivé…”.
Úloha
Chata má iba jeden záchod. Každú hodinu vedúci jednotne náhodne vyžrebujú jedného účastníka alebo účastníčku, ktorej umožnia návštevu toalety. Vediac dĺžku trvania sústredenia a počet účastníkov, Emma by rada vedela odpoveď na nasledovnú otázku. Koľko možných žrebovaní má za následok, že práve jedna osoba navštívi toaletu najviackrát zo všetkých?
Formát vstupu
Na prvom riadku sa nachádza číslo \(t\) – počet sústredení. Na \(i\)-tom z nasledovných \(t\) riadkov sa nachádzajú čísla \(n_i, k_i\) – počet účastníkov a počet hodín \(i\)-teho sústredenia.
Formát výstupu
Vypíšte \(t\) riadkov. Na \(i\)-tom z nich odpoveď na \(i\)-tu otázku modulo \(10^9 + 7\).
Hodnotenie
Úloha má 8 sád vstupov. Platia v nich nasledovné obmedzenia:
| 1 | 2 | 3 | 4,5 | 6 | 7,8 | |
|---|---|---|---|---|---|---|
| \(1 \leq t \leq\) | 10 | 10 | 10 | 10 | 3 | 10 |
| \(1 \leq n \leq\) | 10 | 100 | 4 | 50 | 100 | 100 |
| \(1 \leq k \leq\) | 10 | 4 | 100 | 50 | 100 | 100 |
Príklady
Input:
4
2 2
6 10
5 9
4 4Output:
2
2472
600
28V prvom prípade môže ísť na záchod dvakrát prvý účastník, alebo dvakrát druhá účastníčka. Vo všetkých ostatných možnostiach by nešla na toaletu najviac krát práve jedna osoba.
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.