Submission #13534282

---

Source Code Expand

/*input
10
3 2
3 2
-1 1
2 -1
-3 -9
-8 12
7 7
8 1
8 2
8 4
*/

#include <bits/stdc++.h>
using namespace std;
 
 
 
#define int long long int
#define rep(i,n) \
    for(int i = 0; i < n; i++)
#define rep2(i, a, b) \
    for(int i = a; i < b; i++)
#define all(c) \
    c.begin(), c.end()
#define init(arr, num) \
    memset(arr, num, sizeof(arr))
#define fast\
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define inputFile \
    freopen("input.txt", "r", stdin); 
#define outputFile \
    freopen("output.txt", "w", stdout);
#define modM 1000000007
#define PI 3.1415926535897932

#ifdef Voneone
#define TRACE
#endif
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
    cout << name << " : " << arg1 << std::endl;

}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ','); 
    cout.write(names, comma - names) << " : " << arg1 << " | "; 
    __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

 
typedef long long ll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef pair< int, int > ii;
typedef unordered_set<int> usi;
 

ii reduce(int x, int y){
    if(x == 0) return {0,1};
    if(y == 0) return {1,0};

    int g = __gcd(abs(x), abs(y));

    if(y > 0)
        return {x/g, y/g};
    else
        return {-x/g, -y/g};

}


ii inverse(ii p){


    return reduce(-p.second, p.first);

}

int modpower(int x, unsigned int y, int p) 
{ 
    int res = 1;      // Initialize result 
  
    x = x % p;  // Update x if it is more than or  
                // equal to p 
  
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x) % p; 
  
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x) % p;   
    } 
    return res; 
} 

void solve() 
{ 

    
    int n;
    cin >> n;

    int inv = 0;

    map<ii, int> freq;

    rep(i, n){
        int a , b;
        cin >> a >> b;

        if(a == 0 && b == 0){
            inv++;
            inv %= modM;
        }

        else{
            // auto inv = reduce(a,b);
            // trace(a, b, inv.first, inv.second);
            freq[reduce(a,b)]++;
        }


    }

    int ans = 1;

    set<ii> vis;

    for(auto x : freq){

        auto y = inverse(x.first);

        if(vis.count(x.first) || vis.count(y))
            continue;



        auto pos = freq.find(y);
        if(pos == freq.end()){
            ans *= modpower(2, x.second, modM);
            ans %= modM;
            vis.insert(x.first);
            trace(x.first.first, x.first.second, x.second);
        }else{

            int tmp = (modpower(2, x.second, modM) + modpower(2, pos->second, modM) - 1)%modM;
            ans *= tmp;
            ans %= modM;
            vis.insert(x.first);
            vis.insert(pos->first);
            trace(x.first.first, x.first.second, x.second, pos->first.first, pos->first.second, pos->second);
        }


    }

    if(inv){
        ans *= (inv+1)%modM;
        ans %= modM;
        // cout << ans;
        // return;
    }

    cout << ans-1;



} 
 
 
 
 
signed main()
{
 
    
    #ifdef _DEBUG
    inputFile;
    #endif
    #ifndef __CINP
    fast;
    #endif


    int T = 1;
    // cin >> T;
    while(T--){
        solve();
        cout << endl;
        
        

    }
    
    
    return 0;
 
}


 

Submission Info

Judge Result