#3581. 扑克牌

题目描述

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

输入格式

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

输出格式

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

样例

样例输入

Sample Input 1:  

3  

0 0  

0 0  

0 0  

  

Sample Input 2:  

3  

0 1  

0 2  

1 2  

样例输出

Sample Output 1:  

6  

Sample Output 2:  

2  

数据范围与提示

n<=30，最多只会有3种颜色，且不会有4张牌的数字和颜色都一样。