Description

给定三维空间中n个整点，满足同一个x坐标不会有超过8个点。若两整点距离为1，则它们之间可以互达。求长度大于2的简单环的个数。答案模1000000007。

Format

Input

第一行，n。 下面n行，每行三个整数，表示坐标。

Output

一个数，表示答案。

Samples

8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

28

数据范围

30%的数据 0<=y<8 0<=z<1

另30%的数据 0<=y<4 0<=z<2

100%的数据 n<=400 坐标绝对值<=10^9