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

Є дванадцять типів плиток як показано на Рис. 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-го типу, які у Вас є у наявності.

Вихідні дані

Вивести шукану кількість способів.

Приклади