CF1594E2 Rubik's Cube Coloring (hard version)

这是该问题的困难版本。不同之处在于，在本版本中，有一些节点的颜色已经被选定。 Theofanis 很饿，他想吃他最喜欢的食物 sheftalia。然而，他必须先完成作业。你能帮他解决这个问题吗？ 你有一棵完美的二叉树，共有 $2^k - 1$ 个节点——也就是说，对于所有 $i$ 满足 $1 \leq i \leq 2^{k-1} - 1$，节点 $i$ 有且仅有两个孩子，分别是 $2i$ 和 $2i+1$。编号从 $2^{k-1}$ 到 $2^k-1$ 的节点没有任何孩子。你需要用魔方的 $6$ 种颜色（白色、绿色、红色、蓝色、橙色和黄色）来给这些节点染色。 我们称一种染色方案是“好的”，当且仅当所有相邻节点的颜色在魔方上是相邻的面。 更正式地说： - 白色节点不能与白色和黄色节点相邻； - 黄色节点不能与白色和黄色节点相邻； - 绿色节点不能与绿色和蓝色节点相邻； - 蓝色节点不能与绿色和蓝色节点相邻； - 红色节点不能与红色和橙色节点相邻； - 橙色节点不能与红色和橙色节点相邻； 然而，树中有 $n$ 个特殊节点，它们的颜色已经被选定。 你需要计算该二叉树的所有“好”的染色方案数。只要有至少一个节点颜色不同，就认为两个染色方案不同。 答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

第一行包含整数 $k$（$1 \leq k \leq 60$），表示你需要染色的完美二叉树的层数。 第二行包含整数 $n$（$1 \leq n \leq \min(2^k - 1, 2000)$），表示已经确定颜色的节点数。 接下来的 $n$ 行，每行包含一个整数 $v$（$1 \leq v \leq 2^k - 1$）和一个字符串 $s$，分别表示节点编号和该节点的颜色（$s$ 为 white、yellow、green、blue、red 或 orange 之一）。 保证每个节点 $v$ 在输入中最多出现一次。

输出一个整数，表示不同的“好”染色方案数，对 $10^9+7$ 取模。

下图展示了第一个测试样例的一种合法染色方案。  由 ChatGPT 4.1 翻译