6. Diskrétny Banket

Okäň “Bzučiak” Hruškový, zákerný zločinec známy celou galaxiou, už má vyhliadnutý blištivý cieľ svojej najnovšej lúpeže. Kdesi v bode v nekonečne sa totiž nachádza legendárna planéta menom Al-Jabr, na ktorej sídli mocný panteón známy ako Okruh Celých Čísel. Bzučiak plánuje stať sa lupičom lupičov, spáchať krádež krádeží - ukradne identitu identity. Teda, povedané ako človek, ukradne identitu čísla Jeden. Na to sa vláme na prestížny diskrétny banket, ktorý Jednotka pravidelne organizuje…

Na diskrétny banket Jednotka okrem seba pozve ešte aj nejakú konečnú množinu kladných ¹ celých čísel. Vrátnik dostane krásne očíslovaný zoznam, na ktorom sú všetky tieto čísla vypísané v rastúcom poradí ². Vyzerá to napríklad takto: 1. \(2\) 2. \(3\) 3. \(7\) 4. \(9\) 5. \(10\) 6. \(12\) 7. \(13\)

Môžete si všimnúť, že to je mierne mätúci formát. A vrátnik s ním má problém tiež! Podľa protokolu by sa malo prichádzajúce číslo preukázať dokladom totožnosti, na čo vrátnik skontroluje, či je na zozname, a ak áno, dá mu menovku s jeho menom a vpustí ho na banket. Avšak vrátnik tomuto protokolu zle porozumel, a na menovku dá namiesto jeho názvu jeho poradové číslo na zozname. Teda ak by za vrátnikom so zoznamom vyššie prišlo číslo \(10\), dostane menovku s číslom \(5\), pretože je v zozname piate.

Bzučiakov plán je veľmi jednoduchý, podľa nasledovného krásne očíslovaného zoznamu: 1. Vyhliadnuť si vhodné celé ciele ☑ 1. Ukradnúť identitu niektorého z nich ☐ 2. Podstrčiť vrátnikovi vhodný falošný zoznam hostí ☐ 3. Vstúpiť na banket so svojou novoukradnutou identitou ☐ 4. Dostať menovku (vďaka chybe v systéme s nižším číslom) ☐ 5. Vstúpiť znovu na banket, preukázajúc sa novozískanou menovkou ☐ 6. Opakovať kroky \(4-5\) kým sa bude dať ☐ 7. Získať menovku s číslom \(1\) ☐ 8. Ujsť na Vesmírne Belize ☐ 9. Zo všetkých zločincov, ktorí sa kedy v galaxií činili, byť \(1\) ☐ 10. Kúpiť si zvlhčovač vzduchu ☐

Prvý krok už splnil - má zoznam čísel, ktorých identitu je schopný odcudziť. Teraz potrebuje vašu pomoc ³, aby sa rozhodol, ktorú z počiatočných identít sa mu oplatí ukradnúť najviac. Musí totiž myslieť aj na nasledujúci krok, a podstrčiť vyhovujúci zoznam hostí. Naviac je tu ešte problém s tým, že niektoré čísla vyzerajú veľmi ikonicky a ani Bzučiak, majster prestrojenia, nemusí byť schopný ich výzor napodobniť… Pre každú možnosť počiatočnej identity Bzučiakovi povedzte, koľko existuje zoznamov spĺňajúcich tieto (krásne očíslované) podmienky: 1. Aby to nebolo podozrivé, Bzučiakova pôvodná identita musí byť najvyšším (posledným) číslom v zozname. 2. Opakovaným nahrádzaním čísla jeho poradím v zozname sa po konečnom počte krokov dostaneme na číslo \(1\). 3. Ani jedno z čísel navštívených takýmto skákaním nepatrí medzi tzv. bezpečné čísla, ktoré sú zadané na vstupe.

Úloha

Na vstupe je zadaných niekoľko bezpečných čísel a niekoľko počiatočných čísel. Pre každé počiatočné číslo \(a\) vypíšte počet rôznych podmnožín \(Z\) množiny \({2,3...a}\) takých, že vzostupným zoradením a očíslovaním (od \(1\)) prvkov \(Z\) sa opakovaným nahrádzaním čísla (počnúc od \(a\)) jeho poradovým číslom dostaneme k číslu \(1\) bez toho, aby sme prešli bezpečným číslom, alebo číslom, ktoré nie je v \(Z\).

Keďže počty možností môžu byť fakt veľké, vypíšte iba ich zvyšok po delení číslom \(10^9 + 7\)

Formát vstupu

V prvom riadku vstupu sú medzerou oddelené dve čísla \(r\) a \(k\) (\(0 \leq r \leq 10^5\), \(1 \leq k \leq 10^5\)) - počet bezpečných čísel a počet počiatočných čísel.

Na nasledujúcich \(r\) riadkoch je na každom jedno celé číslo \(x_i\) - toto sú bezpečné čísla. Môžete predpokladať, že sú zoradené od najmenšieho, a žiadne dve sa nerovnajú.

Na \(k\) zvyšných riadkoch je po jednom celom čísle \(a_i\) - všetky počiatočné čísla. To isté počiatočné číslo sa môže vyskytnúť aj viackrát.

V jednotlivých sadách platia nasledujúce obmedzenia:

V sade 1 dokonca platí, že bezpečné nie sú žiadne čísla, teda \(r = 0\).

Formát výstupu

Pre každé z \(k\) počiatočných čísel vypíšte jeden riadok s jediným číslom - počtom vyhovujúcich zoznamov pre dané počiatočné číslo.

Príklady

Input:

0 3
2
5
10

Output:

1
5
77

Pre 2 je odpoveď zrejmá - existuje len jedna prípustná množina, a 2 je v nej najnižším číslom. 5 vyhovujú nasledovné množiny: {2,3,4,5}, {2,3,5}, {2,5}, {3,4,5} a {5}.

Input:

2 3
2
4
2
5
10

Output:

0
2
23

Keďže 2 je bezpečným číslom, začať plán ním by okamžite zlyhalo. 5 vyhovujú tie množiny ako v minulom prípade, ale nesmie v nich byť navštívené 2 ani 4 (môžu byť v zozname, len im nesmieme vziať identitu): {3,4,5} a {5}.