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
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
//{{{ read()
inline ll read(){
	register ll x=0,f=1;
	register char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')	f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')	x=x*10+(ch^48),ch=getchar();
	return x*f;
}
//}}}
const int P=1e9+7;
const int N=2e5+5;
typedef pair<ll,ll> pi;
ll fsp(ll x,int y){
	ll ans=1;
	while(y){
		if(y&1)	ans=ans*x%P;
		x=x*x%P,y>>=1;
	}
	return ans;
}
ll gcd(ll a,ll b){
	while(b){
		ll t=b;
		b=a%b,a=t;
	}
	return a;
}
int n;
ll a[N],b[N];
map<pi,int>ma;
int cnt,cnt2,cnt3;
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read(),b[i]=read();
		if(!a[i]||!b[i]){
			if(a[i]==0&&b[i]==0) ++cnt;
			else	if(a[i]==0)	++cnt2;
			else	if(b[i]==0)	++cnt3;
			--i,--n;
			continue;
		}
		ll g=gcd(abs(a[i]),abs(b[i]));
		if(b[i]<0)	b[i]=-b[i],a[i]=-a[i];
		a[i]/=g,b[i]/=g,ma[pi(a[i],b[i])]++;
	}
	ll ans=(fsp(2,cnt2)+fsp(2,cnt3)-1)%P;
	for(int i=1;i<=n;i++){
		if(!ma[pi(a[i],b[i])])	continue;

		ll x=-b[i],y=a[i];
		if(y<0)	y=-y,x=-x;

		ans=(ans*(fsp(2,ma[pi(a[i],b[i])])+fsp(2,ma[pi(x,y)])-1))%P;
		ma[pi(a[i],b[i])]=ma[pi(x,y)]=0;
	}
	cout<<(ans+cnt-1+P)%P;
	return 0;
}
