There are a set of points S on the plane. This set doesn't contain the origin O(0, 0), and for each two distinct points in the set A and B, the triangle OAB has strictly positive area.

Consider a set of pairs of points (P1, P2), (P3, P4), ..., (P2k - 1, P2k). We'll call the set good if and only if:

  * k ≥ 2. 
  * All Pi are distinct, and each Pi is an element of S. 
  * For any two pairs (P2i - 1, P2i) and (P2j - 1, P2j), the circumcircles of triangles OP2i - 1P2j - 1 and OP2iP2j have a single common point, and the circumcircle of triangles OP2i - 1P2j and OP2iP2j - 1 have a single common point. 



Calculate the number of good sets of pairs modulo 1000000007 (109 + 7).

Input

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of points in S. Each of the next n lines contains four integers ai, bi, ci, di (0 ≤ |ai|, |ci| ≤ 50; 1 ≤ bi, di ≤ 50; (ai, ci) ≠ (0, 0)). These integers represent a point <image>.

No two points coincide.

Output

Print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

Examples

Input

10
-46 46 0 36
0 20 -24 48
-50 50 -49 49
-20 50 8 40
-15 30 14 28
4 10 -4 5
6 15 8 10
-20 50 -3 15
4 34 -16 34
16 34 2 17


Output

2


Input

10
30 30 -26 26
0 15 -36 36
-28 28 -34 34
10 10 0 4
-8 20 40 50
9 45 12 30
6 15 7 35
36 45 -8 20
-16 34 -4 34
4 34 8 17


Output

4


Input

10
0 20 38 38
-30 30 -13 13
-11 11 16 16
30 30 0 37
6 30 -4 10
6 15 12 15
-4 5 -10 25
-16 20 4 10
8 17 -2 17
16 34 2 17


Output

10
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const int MOD = 1000000007;
int n, pot[1000100];
pair<double, double> a[1010];
bool cmp(const pair<double, double> &A, const pair<double, double> &B) {
  if (abs(A.first - B.first) > eps) return A.first < B.first;
  if (abs(A.second - B.second) > eps) return A.second < B.second;
  return 0;
}
struct seg {
  double x, y, ang;
  seg() {}
  seg(pair<double, double> A, pair<double, double> B) {
    x = A.first + B.first;
    y = A.second + B.second;
    ang = atan2(A.second - B.second, A.first - B.first);
  }
  seg(double ang) : ang(ang) {}
  bool operator<(const seg &A) const {
    if (abs(x - A.x) > eps) return x < A.x;
    if (abs(y - A.y) > eps) return y < A.y;
    if (abs(ang - A.ang) > eps) return ang < A.ang;
    return 0;
  }
};
vector<seg> V;
vector<int> cnt;
int calc() {
  int ret = 1, sum = 0;
  for (int i = 0; i < (int)cnt.size(); ++i)
    ret = ((long long)ret * (cnt[i] + 1)) % MOD, sum += cnt[i];
  return (ret - 1 - sum + MOD) % MOD;
}
int main() {
  pot[0] = 1;
  for (int i = 1; i < 1000005; ++i) pot[i] = (long long)pot[i - 1] * 2 % MOD;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    int A, B, C, D;
    scanf("%d%d%d%d", &A, &B, &C, &D);
    double x = (double)A / B, y = (double)C / D;
    double X = x / (x * x + y * y), Y = y / (x * x + y * y);
    a[i] = pair<double, double>(X, Y);
  }
  sort(a, a + n, cmp);
  for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j) {
      V.push_back(seg(a[i], a[j]));
    }
  sort(V.begin(), V.end());
  V.push_back(seg(-100));
  int ans = 0;
  cnt.push_back(1);
  for (int i = 1; i < (int)V.size(); ++i) {
    if (abs(V[i].x - V[i - 1].x) > eps || abs(V[i].y - V[i - 1].y) > eps) {
      ans = (ans + calc()) % MOD;
      cnt.clear();
      cnt.push_back(1);
    } else if (abs(V[i].ang - V[i - 1].ang) > eps)
      cnt.push_back(1);
    else
      ++cnt.back();
  }
  printf("%d\n", ans);
  return 0;
}
