cuburi

Джони обича да си играе на кубчета. Той има неограничено много кубчета от два вида: бели и черни. Размерите на всички кубчета са еднакви и всичките им ръбове са с дължина един метър.

За да построи сграда, Джони нарежда кубчетата на N нива, всяко съдържащо 2*2 кубчета. Така той образувал сграда с височина N, ширина 2 и дължина 2. След това, Джони видял, че сградата ще бъде красива, ако тя има свързана компонента, съставена само от бели кубчета и те да са поне K броя.

Казваме, че две кубчета X и Y принадлежат на една и съща свързана компонента, ако

·         X и Y се намират на съседни позиции (т.е. имат обща стена)

·         X е съседен на кубчето Z и Z се намира в същата компонента на свързаност, в която е Y.

Задача

Определете броя на красивите сгради, които могат да бъдат построени. Резултатът трябва да бъде изведен по модул 10000.

Вход

Входният файл cuburi.in съдържа на първия си ред двете положителни цели числа N и K, разделени с интервал.

Изход

Изходният файл cuburi.out трябва да съдържа търсения брой по модул 10000.

Ограничения

1 <= N <= 40
• 1 <= K <= 4*N

Примери

cuburi.in

cuburi.out

Обяснение

3 12

1

Единствена сграда, съставена само от бели кубчета.

 

cuburi.in

cuburi.out

Обяснение

 

4 15

17

Съществуват 17 сгради, всяка съдържаща общо по 16 кубчета. Шестнадесет от тези сгради са съставени от по 15 бели кубчета и едно черно, а седемнадесетата е съставена само от бели кубчета.

 

cuburi.in

cuburi.out

6 15

2244

 Време за работа на програмата: 0.6 секунди за тест

Daniel Pasaila
"Al. I Cuza" University, Iaşi
IT Department
danielpasaila@yahoo.com

Превод на български: Емил Келеведжиев