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.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Random;

public class Main {

    private static final long MOD = 1_000_000_007;

    public static void main(String[] args) throws Exception {
        try (BufferedInputStream in = new BufferedInputStream(System.in);
             PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out))) {

            _Scanner sc = new _Scanner(in);
            
            // 21:56-
            
            Map<X, Integer> map = new LinkedHashMap<>();
            List<X> list = new ArrayList<>();
            int n = sc.nextInt();
            long ans = 0L;
            for (int i = 0; i < n; i++) {
                long a = sc.nextLong();
                long b = sc.nextLong();
                if (a == 0 && b == 0) {
                    ans++;
                    continue;
                }
                long gcd = gcd(a, b);
                X x = new X((long) Math.signum(Math.signum(a) * Math.signum(b)), Math.abs(a / gcd), Math.abs(b / gcd));
                if (x.a == 0) x.sig = 1;
                if (x.b == 0) x.sig = -1;
                list.add(x);
                map.merge(x, 1, Integer::sum);
            }

            long[] pows = new long[n + 1];
            pows[0] = 1;
            for (int i = 1; i < pows.length; i++) pows[i] = (pows[i - 1] * 2) % MOD;

            long total = 1;
            for (X x : list) {
                int a = map.getOrDefault(x, 0);
                int b = map.getOrDefault(new X(-x.sig, x.b, x.a), 0);
                map.put(x, 0);
                map.put(new X(-x.sig, x.b, x.a), 0);

                total = (total * ((pows[a] + pows[b] - 1) % MOD)) % MOD;
            }

            total = (MOD + total - 1) % MOD;
            total = (total + ans) % MOD;

            out.println(total);
        }
    }

    private static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    private static class X {
    	long sig, a, b;

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

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            X x = (X) o;
            return sig == x.sig &&
                    a == x.a &&
                    b == x.b;
        }

        @Override
        public int hashCode() {
            return Objects.hash(sig, a, b);
        }

        @Override
        public String toString() {
            return "X{" +
                    "sig=" + sig +
                    ", a=" + a +
                    ", b=" + b +
                    '}';
        }
    }

    

    private static void reverse(int[] vs) {
        for (int i = 0; i < vs.length / 2; i++) {
            swap(vs, i, vs.length - 1 - i);
        }
    }

    static class _Scanner {
        InputStream is;
        _Scanner(InputStream is) {
            this.is = is;
        }
        byte[] bb = new byte[1 << 15];
        int k, l;
        byte getc() {
            try {
                if (k >= l) {
                    k = 0;
                    l = is.read(bb);
                    if (l < 0) return -1;
                }
                return bb[k++];
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        byte skip() {
            byte b;
            while ((b = getc()) <= 32)
                ;
            return b;
        }

        int nextInt() {
            int n = 0;
            int sig = 1;
            for (byte b = skip(); b > 32; b = getc()) {
                if (b == '-') {
                    sig = -1;
                } else {
                    n = n * 10 + b - '0';
                }
            }
            return sig * n;
        }

        long nextLong() {
            long n = 0;
            long sig = 1;
            for (byte b = skip(); b > 32; b = getc()) {
                if (b == '-') {
                    sig = -1;
                } else {
                    n = n * 10 + b - '0';
                }
            }
            return sig * n;
        }

        public String next() {
            StringBuilder sb = new StringBuilder();
            for (int b = skip(); b > 32; b = getc()) {
                sb.append(((char) b));
            }
            return sb.toString();
        }
    }

    private static void shuffle(int[] ar) {
        Random rnd = new Random();
        for (int i = 0; i < ar.length; i++) {
            int j = i + rnd.nextInt(ar.length - i);
            swap(ar, i, j);
        }
    }

    private static void shuffle(Object[] ar) {
        Random rnd = new Random();
        for (int i = 0; i < ar.length; i++) {
            int j = i + rnd.nextInt(ar.length - i);
            swap(ar, i, j);
        }
    }

    private static void swap(int[] ar, int i, int j) {
        int t = ar[i];
        ar[i] = ar[j];
        ar[j] = t;
    }

    private static void swap(Object[] ar, int i, int j) {
        Object t = ar[i];
        ar[i] = ar[j];
        ar[j] = t;
    }


}
