← 返回题目列表

Codeforces · 1594/E2

E2. 魔方着色(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。不同之处在于,在这个版本中,有些节点已经选择了颜色。

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

注意

在下图中,您可以看到第一个测试示例的正确着色之一。