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:

Príklady

Input:

4
2 2
6 10
5 9
4 4

Output:

2
2472
600
28

V 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.