联盟

题目描述

在国际会议上，共有 n 个国家需要加入三个联盟中的一个。任何两个接壤的国家不能加入相同的联盟。现在给出各国的接壤情况，请计算存在多少种合法的联盟分配方案。

输入格式

第一行：单个整数 n 表示国家数量

第二行到第 n 行：在第i+1 行有 n-i 个整数 ci,i+1,ci,i+2,…,ci,n，其中

ci,j=0-表示 i 号国家与 j 号国家不接壤

ci,j=1 表示 i 号国家与 j 号国家接壤

输出格式

单个整数：表示合法的联盟分配方案总数。

输入样例#1

3
1 1
1

输出样例#1

6

输入样例#2

4
1 1 1
1 1
1

输出样例#2

0

说明提示

数据范围

对于 50% 的数据，1≤n≤12

对于 100% 的数据，1≤n≤20

样例1说明

三国两两接壤，形成三角形。三个联盟的排列方案为 3!=6种。

限制

时间限制：1000ms

内存限制：512MiB