eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Слони

Слони

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Слон - це шахова фігура, якою грають на квадратній дошці. Слон може пересуватись лишн по діагоналі, а два слони можут атакувати один одного лише якщо один з них знаходиться на шляху іншого. На рисунку темними квадратами позначено клітинки, у які може піти слон B1 зі своєї поточної позиції. Слони B1 та B2 атакують один одного, а B1 та B3 - ні. B2 та B3 не атакують один одного.

За заданими числам n та k визначіть кількість способів, якими можна розставити k слонів на шаховій дошці розміром n×n так, щоб ніякі два з них не били один одного.

Вхідні дані

Кожен рядок є окремим тестом і містить два цілих числа n (1n30) та k (0kn^2). Останній тест містить два нулі и не опрацьовується.

Вихідні дані

Для кожного тесту у окремому рядку виведіть кількість способів, якими можна розмістити задане число слонів на шаховій дошці заданого розміру так, щоб ніякі два слони не били один одного. Відомо, що відповідь завжди буде меншою 10^15.

Приклад

Вхідні дані #1
8 6
4 4
20 40
30 5
0 0
Вихідні дані #1
5599888
260
0
3127859642656