There are n lattice points in the 3D space. One point can get to another if and only if their Euclid distance is 1. Find out the number of simple cycles (that has length > 2). The number of points with same x coordinates do not exceed 8. 

Input

First line, n. 

Following are n lines, each describes one point, no two points share same coordinates. 

n<=400, coordinates in range [-10^9, 10^9] (inclusive).

Output

One number, the required answer mod 1000000007. 

Example

Input:
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

Output:
28