这是问题的困难版本。不同之处在于,在这个版本中,有些节点已经选择了颜色。
Theofanis 饿了,他想吃他最喜欢的食物,sheftalia。不过,他应该先完成作业。你能帮他解决这个问题吗?
您有一个由 $$$2^k - 1$$$ 节点组成的完美二叉树 - 一个二叉树,其中从 $$$1$$$ 到 $$$2^{k - 1} - 1$$$ 的所有顶点 $$$i$$$ 恰好有两个子节点:顶点 $$$2i$$$ 和 $$$2i + 1$$$。从 $$$2^{k - 1}$$$ 到 $$$2^k - 1$$$ 的顶点没有任何子节点。您想要使用 $$$6$$$ 魔方颜色(白色、绿色、红色、蓝色、橙色和黄色)为其顶点着色。
当所有边连接的节点的颜色都是魔方中相邻边的颜色时,我们称着色为好。
魔方图片及其 2D 地图。
更正式地说:
- 白色节点不能与白色和黄色节点相邻;
- 黄色节点不能与白色和黄色节点相邻;
- 绿色节点不能与绿色和蓝色节点相邻;
- 蓝色节点不能与绿色和蓝色节点相邻;
- 红色节点不能与红色和橙色节点相邻;
- 橙色节点不能与红色和橙色节点相邻;
然而,树中有 $$$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$$$ 是白色、黄色、绿色、蓝色、红色和橙色之一)。
保证每个节点 $$$v$$$ 在输入中最多出现一次。
输出
打印一个整数——不同颜色的数量以 $$$10^9+7$$$ 为模。
示例
输入 #1
3 2 5 orange 2 white
输出 #1
1024
输入 #2
2 2 1 white 2 white
输出 #2
0
输入 #3
10 3 1 blue 4 red 5 orange
输出 #3
328925088
注意
在下图中,您可以看到第一个测试示例的正确着色之一。