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 <map>
#include <cstdio>
#include <algorithm>
#define FOR(i,a,b) for(register int i=(a);i<(b);++i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
const ll p = 1000000007;
const int maxn = 200005;
int n;
map<pi,ll>mp;
map<pi,bool>vis;
ll gcd(ll a,ll b){
	return b==0?a:gcd(b,a%b);
}
ll qpow(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1ll)ans=(ans*a)%p;
		a=(a*a)%p;
		b>>=1ll;
	}
	return ans;
}
int main(){
	scanf("%d",&n);
	ll zero_cnt=0;
	FOR(i,0,n){
		ll a,b;
		scanf("%lld%lld",&a,&b);
		if(!a&&!b){
			zero_cnt++;
			continue;
		}
		ll c=gcd(a,b);
		a/=c,b/=c;
		if(b<0)a=-a,b=-b;
		if(b==0)a=-1;else if(a==0)b=1;
		mp[pi{a,b}]++;
	}
	map<pi,ll>::iterator it;
	ll ans=1;
	for(it=mp.begin();it!=mp.end();++it){
		pi pp = it->first;
		pp = pi{-pp.second,pp.first};
		if(pp.second<0)pp=pi{-pp.first,-pp.second};
		if(vis[pp] || vis[it->first])continue;
		ll num1=mp[it->first],num2=mp[pp];
		ll add=(qpow(2,num1)+qpow(2,num2)-1ll)%p;
		ans=(ans*add)%p;
		vis[pp]=vis[it->first]=true;
	}
	ans+=zero_cnt-1ll;
	ans%=p;
	printf("%lld\n",(ans+p)%p);
}