CF1594E2.Rubik's Cube Coloring (hard version)

It is the hard version of the problem. The difference is that in this version, there are nodes with already chosen colors.

Theofanis is starving, and he wants to eat his favorite food, sheftalia. However, he should first finish his homework. Can you help him with this problem?

You have a perfect binary tree of $2^k - 1$ nodes — a binary tree where all vertices $i$ from $1$ to $2^{k - 1} - 1$ have exactly two children: vertices $2i$ and $2i + 1$. Vertices from $2^{k - 1}$ to $2^k - 1$ don't have any children. You want to color its vertices with the $6$ Rubik's cube colors (White, Green, Red, Blue, Orange and Yellow).

Let's call a coloring good when all edges connect nodes with colors that are neighboring sides in the Rubik's cube.

A picture of Rubik's cube and its 2D map.

More formally:

• a white node can not be neighboring with white and yellow nodes;
• a yellow node can not be neighboring with white and yellow nodes;
• a green node can not be neighboring with green and blue nodes;
• a blue node can not be neighboring with green and blue nodes;
• a red node can not be neighboring with red and orange nodes;
• an orange node can not be neighboring with red and orange nodes;

However, there are $n$ special nodes in the tree, colors of which are already chosen.

You want to calculate the number of the good colorings of the binary tree. Two colorings are considered different if at least one node is colored with a different color.

The answer may be too large, so output the answer modulo $10^9+7$.

这是该问题的困难版本。区别在于，在此版本中，部分节点的颜色已经预先选定。

西奥法尼斯饿了，他想吃自己最爱的食物——希夫塔利亚香肠（sheftalia）。然而，他必须先完成家庭作业。你能帮他解决这个问题吗？

你有一棵包含 $2^k - 1$ 个节点的完美二叉树——即一棵二叉树，其中所有编号从 $1$ 到 $2^{k - 1} - 1$ 的顶点 $i$ 均恰好有两个子节点：顶点 $2i$ 和 $2i + 1$；而编号从 $2^{k - 1}$ 到 $2^k - 1$ 的顶点均无子节点。你需要用魔方的六种颜色（白色、绿色、红色、蓝色、橙色和黄色）对这棵树的所有顶点进行染色。

若一棵树的所有边所连接的两个顶点的颜色，在魔方中恰好为相邻面，则称该染色方案为合法染色。

魔方实物图及其二维展开图。

更形式化地，约束如下：

• 白色顶点不能与白色或黄色顶点相邻；
• 黄色顶点不能与白色或黄色顶点相邻；
• 绿色顶点不能与绿色或蓝色顶点相邻；
• 蓝色顶点不能与绿色或蓝色顶点相邻；
• 红色顶点不能与红色或橙色顶点相邻；
• 橙色顶点不能与红色或橙色顶点相邻；

然而，树中有 $n$ 个特殊节点，其颜色已预先固定。

你需要计算该二叉树的合法染色方案总数。若至少有一个节点的颜色不同，则认为两种染色方案不同。

答案可能非常大，请输出结果对 $10^9+7$ 取模后的值。

The first line contains the integers $k$ ($1 \le k \le 60$) — the number of levels in the perfect binary tree you need to color.

The second line contains the integer $n$ ($1 \le n \le \min(2^k - 1, 2000)$) — the number of nodes, colors of which are already chosen.

The next $n$ lines contains integer $v$ ($1 \le v \le 2^k - 1$) and string $s$ — the index of the node and the color of the node ($s$ is one of the white, yellow, green, blue, red and orange).

It is guaranteed that each node $v$ appears in the input at most once.

第一行包含整数 $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$ 在输入中至多出现一次。

Print one integer — the number of the different colorings modulo $10^9+7$.

输出一个整数——不同染色方案的数量对 $10^9+7$ 取模的结果。

In the picture below, you can see one of the correct colorings of the first test example.

在下面的图片中，您可以看到第一个测试样例的一种正确染色方案。