050-A.md

Даалуу шахах

Танд дөрвөлжин шугамтай $M × N$ хэмжээтэй тэгш өнцөгт самбар болон $2 × 1$ хэмжээтэй төгсгөлгүй олон даалуунууд өгөгдсөн. Даалууг эргүүлж болно. Даалууг самбар дээр байрлуулахдаа дараах дүрмүүдийг дагана:

1. Даалуу бүр яг хоёр дөрвөлжинг халхлана.
2. Аль ч хоёр даалуу давхардаж байрлахгүй.
3. Даалуу самбараас халихгүй дотор нь байрлана.

Тийм бол байрлуулж болох даалууны хамгийн их утгыг ол.

Оролт

Нэг мөрөнд самбарын хэмжээг илтгэх $M$, $N$ ($1 ≤ M ≤ N ≤ 16$) хоёр тоо байна.

Гаралт

Хариу болох ганц тоо.

-- gmunkhbaatarmn