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

Планы Трубопроводов

Планы Трубопроводов

Лимит времени 3 секунды
Лимит использования памяти 64 MiB

Имеется двенадцать типов плиток как показано на Рис. 1. Необходимо заполнить таблицу размером R×C ячеек этими плитками. R -количество строк, а C - количество колонок.

Найти количество способов, которыми можно заполнить таблицу, учитывая следующие ограничения:

  • Каждая ячейка покрывается одной плиткой.

  • Центр верхней левой ячейки (1, 1) и центр нижней правой ячейки (C, R) соединены дорогами.

prb5841

Рис. 1: типы плиток

Входные данные

Первая строка содержит два целых числа R и C (**2 **≤ R×**C **≤ 15). Известно, что R или C больше 1.

Вторая строка содержит двенадцать целых чисел t[1], t[2], ..., t[12] (0 ≤ t[1] + … + t[12] ≤ 15). t[i] равно количеству плиток i-го типа, которые у Вас имеются в наличии.

Выходные данные

Вывести искомое количество способов.

Пример

Входные данные #1
3 3
4 2 2 0 0 0 0 0 0 0 0 1
Выходные данные #1
2
Источник JAG Summer 2012, Japan