#3581. 扑克牌

内存限制:512 MiB 时间限制:100 Sec

题目描述

  我们有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张牌的数字和颜色都一样。