在国际会议上，共有 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 种。限制时间限制：1000，内存限制：512000

C++程序题：联盟

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

输入格式

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

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

输出格式

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

输入样例1

3
1 1
1

输出样例1

输入样例2

输出样例2

说明提示

数据范围：

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

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

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

限制

时间限制：1000，内存限制：512000