Замощение прямоугольника m×n доминошками будем называть прочным, если не существует прямой, пересекающей внутренность прямоугольника m×n и не пересекающей внутренность ни одной доминошки.
Например, приведенные на иллюстрации замощения (a) и (b) — прочные, а замощения (c) и (d) — нет.
А сколько существует прочных замощений прямоугольника m×n?
В первой строке два натуральных числа m и n (1 ≤ m ≤ 8; 1 ≤ n ≤ 16) — ширина и высота доски.
Выведите одно число — количество прочных замощений данного прямоугольника.
Приведём все прочные замощения прямоугольника 5×6: