题目描述

给定一个 $n$ 个点的无向图，用三种不同的颜色，为图上每个点分配三种颜色中的一种颜色，一个可行的染色方案要求每条边的两个端点不能分配相同的颜色。请计算，这张图有多少种可行染色方案。

输入格式

• 第一行：单个整数 $n$
• 第二行到第 $n$ 行：在第 $i+1$ 行有 $n-i$ 个整数 $b_{i,i+1},b_{i,i+2},\dots,b_{i,n}$，其中
  • $b_{i,j} = 0$ 表示 $i$ 与 $j$ 没有边相连
  • $b_{i,j} = 1$ 表示 $i$ 与 $j$ 有边相连

输出格式

单个整数：表示可行的染色方案数量。

3
1 1
1

6

样例解释 1

三个点构成一个三角形，每种颜色只能给一个点，排列后有6种方案

4
1 1 1
1 1
1

0

样例解释 2

四个点两两相连，构成一个团，没有三染色的可能

4
1 0 1
1 0
1

18

样例解释 3

四个点构成一个环

5
0 0 0 0
0 0 0
0 0
0

243

样例解释 4

5个点各自独立，3的5次方为243

数据范围

• $50\%$ 的数据，$1\leq n\leq 12$
• $100\%$ 的数据，$1\leq n\leq 20$