题目描述

我们有 $n$ 张纸牌，每张牌都有数字和颜色两个属性。今天我心情不错，想把这 $n$ 张牌排成一行，使得相邻的两个要么颜色相同要么数字相同。数字在 $0$ 到 $9$ 之间，颜色有红黄蓝三种（用 $0,1,2$ 来表示）。想让你求出方案数。

输入格式

第一行输入 $n$，表示有 $n$ 张纸牌。接下来 $n$ 行，每行两个数字分别表示第 $i$ 张牌的颜色和数字。

输出格式

一行输出答案，对 $2^{32}$ 取模。

3
0 0
0 0
0 0

6

3
0 1
0 2
1 2

2

数据规模与约定

对于 $100\%$ 的数据满足 $n\le 30$，最多只会有 $3$ 种颜色，且不会有 $4$ 张牌的数字和颜色都一样。

题目来源

By 佚名提供