Mircea şi Andrei sunt pasionaţi de construcţiile realizate din piese Lego. Fiecare dintre ei are un set format din N cuburi negre de latură 1 şi mai multe piese paralelipipedice de culoare albă cu care va construi o clădire de formă paralelipipedică având baza un pătrat de latură 2 şi înălţimea H.

Toate piesele de culoare albă au înălţimea 2 iar celelalte laturi egale cu 1 şi nu pot fi răsturnate în momentul în care se asamblează pentru a construi clădirea. Aceasta va conţine întotdeauna toate piesele negre din set şi atâtea piese de culoare albă cât e necesar pentru finalizarea ei.

În momentul finalizării clădirii, cei doi băieţi observă că deşi au folosit aceleaşi seturi de piese, cele două clădiri sunt diferite deoarece combinaţiile de culori alb-negru de pe faţadele (nordică, sudică, vestică sau estică) clădirilor nu arată la fel.

Cerința

Scrieţi un program care să calculeze numărul T de clădiri diferite care se pot construi cu piesele date, ştiind că două clădiri sunt identice dacă sunt îndeplinite simultan următoarele condiţii:

• faţada dinspre nord a uneia este identică cu faţada dinspre nord a celeilalte;
• faţada dinspre est a uneia este identică cu faţada dinspre est a celeilalte;
• faţada dinspre sud a uneia este identică cu faţada dinspre sud a celeilalte;
• faţada dinspre vest a uneia este identică cu faţada dinspre vest a celeilalte.

Programul va afişa restul împărţirii numărului T la 666013.

Date de intrare

Fișierul de intrare cladire4.in conține pe prima linie două numere naturale N şi H (în această ordine), separate printr-un spaţiu şi având semnificaţia din enunţ.

Date de ieșire

Fișierul de ieșire cladire4.out va conține pe prima linie un singur număr natural ce reprezintă restul împărţirii numărului T la 666013.

Restricții și precizări

• N, H sunt numere naturale şi N este număr par;
• 2 ≤ N ≤ 4H şi 1 ≤ H ≤ 1000;
• există atâtea piese albe câte sunt necesare;
• o piesă de culoare albă se va aşeza întotdeauna cu baza de latură 1, peste o altă piesă a clădirii sau la baza acesteia;
• cu piesele date se poate construi cel puţin o clădire;
• pentru 30% din teste H ≤ 25.

Exemplu:

cladire4.in

2 2

cladire4.out

4

Explicație

Exemplu:

cladire4.in

4 3

cladire4.out

16