Background

Special for beginners, ^_^

Description

设有下列形状：有n个区域（1 ≤ n≤100 ），各区域的相邻关系用0（不相邻），1（相邻）表示。例如下表的邻接矩阵对应于右图。请输出用4种颜色将地图涂色的所有方案数（要求相邻两点不能涂成相同的颜色）

Format

Input

第一行一个整数N表示图有N个点，接下来N行，每行N个数，第i 行第J列如果为1表示第I个点和第J个点相邻。

Output

输出用4种颜色将地图涂色的所有方案数（要求相邻两点不能涂成相同的颜色）

Samples

4
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

84

Limitation

1s, 1024KiB for each test case.