We have caught N sardines. The deliciousness and fragrantness of the i-th sardine is A_i and B_i, respectively.

We will choose one or more of these sardines and put them into a cooler. However, two sardines on bad terms cannot be chosen at the same time.

The i-th and j-th sardines (i \neq j) are on bad terms if and only if A_i \cdot A_j + B_i \cdot B_j = 0.

In how many ways can we choose the set of sardines to put into the cooler? Since the count can be enormous, print it modulo 1000000007.

Constraints

* All values in input are integers.
* 1 \leq N \leq 2 \times 10^5
* -10^{18} \leq A_i, B_i \leq 10^{18}

Input

Input is given from Standard Input in the following format:


N
A_1 B_1
:
A_N B_N


Output

Print the count modulo 1000000007.

Examples

Input

3
1 2
-1 1
2 -1


Output

5


Input

10
3 2
3 2
-1 1
2 -1
-3 -9
-8 12
7 7
8 1
8 2
8 4


Output

479
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.TreeMap;
import java.util.StringTokenizer;
import java.util.Map;
import java.util.Map.Entry;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ABullet solver = new ABullet();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABullet {
        int mod;

        public long gcd(long a, long b) {
            if (b == 0)
                return a;
            return gcd(b, a % b);
        }

        public void solve(int testNumber, Scanner sc, PrintWriter pw) {
            int n = sc.nextInt();
            mod = (int) 1e9 + 7;
            TreeMap<pair, Integer> map = new TreeMap<>();
            for (int i = 0; i < n; i++) {
                long a = sc.nextLong(), b = sc.nextLong();
                pair temp = makePair(a, b);
                map.put(temp, map.getOrDefault(temp, 0) + 1);
            }
            long ans = 1;
            TreeSet<pair> visited = new TreeSet<>();
            for (Map.Entry<pair, Integer> entry : map.entrySet()) {
                pair p = entry.getKey();
                int c = entry.getValue();
                if (visited.contains(p))
                    continue;
                if (p.a == 0 && p.b == 0) {
                    continue;
                }
                pair incomp;
                if (p.a == 0)
                    incomp = new pair(1, 0);
                else if (p.b == 0)
                    incomp = new pair(0, 1);
                else {
                    int bool = 0;
                    if (-p.b <= 0)
                        bool ^= 1;
                    if (p.a <= 0)
                        bool ^= 1;
                    incomp = new pair((bool == 1 ? -1 : 1) * Math.abs(p.b), Math.abs(p.a));
                }
                visited.add(incomp);
                int c2 = map.getOrDefault(incomp, 0);
                ans *= (fastPowMod(2, c) % mod + fastPowMod(2, c2) % mod - 1 + mod) % mod;
                ans %= mod;
            }
            pw.println((ans - 1 + mod + map.getOrDefault(new pair(0, 0), 0)) % mod);
        }

        private pair makePair(long a, long b) {
            if (a == 0 && b == 0)
                return new pair(0, 0);
            if (a == 0)
                return new pair(0, 1);
            if (b == 0)
                return new pair(1, 0);
            int bool = a < 0 ? 1 : 0;
            bool ^= b < 0 ? 1 : 0;
            a = Math.abs(a);
            b = Math.abs(b);
            long gcd = gcd(a, b);
            return new pair((bool == 1 ? -1 : 1) * a / gcd, b / gcd);
        }

        public long fastPowMod(long a, long b) {
            if (b == 0)
                return 1;
            long temp = fastPowMod(a, b / 2) % mod;
            if (b % 2 == 1)
                return a % mod * temp % mod * temp % mod;
            else
                return temp % mod * temp % mod;
        }

        public class pair implements Comparable<pair> {
            long a;
            long b;

            public pair(long a, long b) {
                this.a = a;
                this.b = b;
            }

            public int compareTo(pair pair) {
                return a == pair.a ? Long.compare(b, pair.b) : Long.compare(a, pair.a);
            }

            public String toString() {
                return "pair{" +
                        "a=" + a +
                        ", b=" + b +
                        '}';
            }

        }

    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}

