6. Egyptské pyramídy

Neferjerry vyšla na balkón jej luxusného sídla. Do tváre jej hneď udrela všade prítomná horúčava Egypta. Rozpálený suchý vzduch bol narušený iba údermi vejárov jej otrokov. Pomaly sa presunula k lehátku skrytom v tieni, ľahla si naň a nechala sa kŕmiť bobuľkami hrozna. Život hlavného architekta faraónov bol plný prepychu a pohodlia.

V poslednom čase ju však trápilo nové zadanie. Postaviť obrovskú Cheopsovu pyramídu bola hračka. Naplniť skrytú hrobku Tutanchamóna kliatbami bola výzva, ale nič čo by nezvládla. To čo však od nej žiadal Tutanjanón bolo takmer nemožné.

Všetci predsa vedia, že pyramída sa stavia z obrovských kamenných blokov tvaru kocky. Z nich sa tvorí \(h\) poschodí pyramídy. Najspodnejšie poschodie je štvorec, ktorého jedna strana má \(x\) blokov, najvrchnejšie poschodie je tvorené jediným blokom. Zvyšné poschodia sú následne pekne vycentrované na stred pyramídy. A doteraz bolo zvykom, že tieto poschodia boli takisto štvorcové.

Nový faraón si však zmyslel, že vôbec nebude vadiť ani keď to budú “takmer štvorce”. A namiesto toho aby ju nechal navrhnúť najkrajšiu takúto pyramídu, rozhodol sa vybrať si ju náhodne. Neferjerry preto povedal, aby zistila, koľko rôznych pyramíd by mohla postaviť, aby vedel, z čoho si vyberá. A hoci kopy pergamenov zapísaných výpočtami sa zväčšujú, Neferjerry nie je o nič bližšie k riešeniu.

Rozmýšľajúc sa pozrela na vás, ako ju ovievate a kŕmite hroznom. Však na čo mať otrokov (čítaj riešiteľov KSP), ak nie na špinavú prácu a nudné výpočty. Rukou prešla po koženom biči, ktorý jej ležal pri nohách a s úsmevom sa otočila na vás: “Mám pre vás úlohu…”

Úloha

Vašou úlohou bude zistiť počet pyramíd, ktoré Neferjerry môže postaviť faraónovi Tutanjanovi. Tieto pyramídy musia spĺňať nasledovné podmienky:

• vrchné poschodie je tvorené jedným blokom
• pyramída má práve \(h\) poschodí
• spodné poschodie je tvorené \(x \times x\) blokmi
• každé poschodie je v oboch rozmeroch aspoň o dva bloky kratšie ako poschodie pod ním (to spôsobí, že keď ich vycentrujeme na stred, tak každé poschodie bude vo všetkých štyroch smeroch aspoň o jeden blok kratšie ako to pod ním a pyramída bude pekná)
• každé poschodie musí byť “takmer štvorec” – to je taký obdĺžnik, v ktorom je absolútna hodnota rozdielu jeho šírky a dĺžky najviac 3 (všimnite si, že štvorec je tiež “takmer” štvorec)

Dve pyramídy považujeme za rôzne ak sa líšia vo veľkosti aspoň jedného poschodia z pohľadu od Cheopsovej pyramídy. To znamená, že pyramída, ktorej tretie poschodie má veľkosť \(3\times 4\) je rozdielna od pyramídy, ktorej tretie poschodie má veľkosť \(4 \times 3\).

Keďže počet takýchto pyramíd môže byť naozaj veľký, vypíšte zvyšok tohto čísla po delení \(1\,000\,000\).

Formát vstupu

Vstup je tvorený dvoma číslami \(h\) a \(x\) (\(2 \leq h \leq 2\,000\), \(3 \leq x \leq 5\,000\)) – prvé určuje výšku pyramídy a druhé veľkosť najspodnejšieho poschodia. Vo všetkých vstupoch platí, že \(x \geq 2\cdot h - 1\), teda vždy sa dá postaviť aspoň jedna taká pyramída.

V jednotlivých sadách navyše platia nasledovné obmedzenia:

Formát výstupu

Na výstup vypíšte jedno číslo – počet pyramíd, ktoré spĺňajú všetky uvedené podmienky, modulo \(1\,000\,000\).

Príklad

Input:

3 7

Output:

9

Vrchné aj spodné poschodia sú jednoznačne určené. Stredné poschodie môže mať nasledovné veľkosti: \(5\times 5\), \(5\times 4\), \(5\times 3\), \(4\times 5\), \(4\times 4\), \(4\times 3\), \(3\times 5\), \(3\times 4\), \(3\times 3\).

Input:

12 23

Output:

1

Každé poschodie musí byť štvorec o dva menší ako poschodie pod ním.

Input:

7 20

Output:

397944