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

输入格式

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

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

1. ci,j = 0 表示 i 号国家与 j 号国家不接壤；

2. 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