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

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

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

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

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

Рис. 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-го типа, которые у Вас имеются в наличии.

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

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

Примеры