| Codeforces Round 747 (Div. 2) |
|---|
| Закончено |
Это сложная версия задачи. Различие состоит в том, что в этой версии есть вершины с уже зафиксированными цветами.
Теофанис ужасно проголодался и хочет, наконец, отведать своего любимого блюда, шефталью. Но сначала ему нужно закончить с домашней работой. Поможете ли вы ему в решении данной задачи?
Вам задано идеальное двоичное дерево из $$$2^k - 1$$$ вершин — двоичное дерево, в котором у всех вершин $$$i$$$ от $$$1$$$ по $$$2^{k - 1} - 1$$$ есть ровно два сына: вершины $$$2i$$$ и $$$2i + 1$$$. У вершин с $$$2^{k - 1}$$$ по $$$2^k - 1$$$ нет детей. Вы хотите покрасить его вершины в $$$6$$$ цветов кубика Рубика (белый, зеленый, красный, синий, оранжевый и желтый).
Назовем раскраску хорошей, если все ребра дерева соединяют вершины, цвета которых являются соседними цветами кубика Рубика.
 |  |
Формально говоря:
- соседними к белой вершине не могут быть белые и желтые вершины;
- соседними к желтой вершине не могут быть белые и желтые вершины;
- соседними к зеленой вершине не могут быть зеленые и синие вершины;
- соседними к синей вершине не могут быть зеленые и синие вершины;
- соседними к красной вершине не могут быть красные и оранжевые вершины;
- соседними к оранжевой вершине не могут быть красные и оранжевые вершины.
Однако, есть $$$n$$$ особых вершин в дереве, цвета которых уже зафиксированы.
Вам нужно посчитать количество хороших раскрасок двоичного дерева. Две раскраски считаются различными, если существует вершина, цвет которой в них различается.
Так как ответ может быть слишком большим, выведите его по модулю $$$10^9+7$$$.
В первой строке задано одно целое число $$$k$$$ ($$$1 \le k \le 60$$$) — количество уровней в идеальном двоичном дереве, которое вам нужно раскрасить.
Во второй строке задано одно целое число $$$n$$$ ($$$1 \le n \le \min(2^k - 1, 2000)$$$) — количество вершин, цвета которых уже выбраны.
В следующих $$$n$$$ строках заданы целое число $$$v$$$ ($$$1 \le v \le 2^k - 1$$$) и строка $$$s$$$ — номер вершины и ее цвет ($$$s$$$ является одной из следующих строк: white, yellow, green, blue, red или orange).
Гарантируется, что каждая вершина $$$v$$$ появляется во входных данных не более одного раза.
Выведите одно целое число — количество различных раскрасок по модулю $$$10^9+7$$$.
3 2 5 orange 2 white
1024
2 2 1 white 2 white
0
10 3 1 blue 4 red 5 orange
328925088
На изображении ниже вы можете видеть одну из корректных раскрасок для первого примера.
