package chelper; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; import java.util.TreeMap; import io.InputReader; import io.OutputWriter; import misc.SimpleSavingChelperSolution; public class E extends SimpleSavingChelperSolution { private int[] x; private int[] y; private int n; private Map xMap; private Map yMap; private List> edges; private boolean[] visited; private long MOD; public void solve(int testNumber, InputReader in, OutputWriter out) { wrapSolve(testNumber, in, out); } @Override public void solve(int testNumber) { n = in.nextInt(); x = new int[n]; y = new int[n]; xMap = new TreeMap<>(); yMap = new TreeMap<>(); edges = new ArrayList<>(); for (int i = 0; i < n; i++) { edges.add(new HashSet<>()); } Map prevX = new HashMap<>(); Map prevY = new HashMap<>(); for (int i = 0; i < n; i++) { x[i] = in.nextInt(); y[i] = in.nextInt(); xMap.put(x[i], xMap.getOrDefault(x[i], 0) + 1); yMap.put(y[i], yMap.getOrDefault(y[i], 0) + 1); Integer pX = prevX.get(x[i]); Integer pY = prevY.get(y[i]); if (pX != null) { edges.get(pX).add(i); edges.get(i).add(pX); } if (pY != null) { edges.get(pY).add(i); edges.get(i).add(pY); } prevX.put(x[i], i); prevY.put(y[i], i); } visited = new boolean[n]; long ans = 1; MOD = 1000000007; for (int i = 0; i < n; i++) { if (visited[i]) { continue; } List res = new ArrayList<>(); dfs(i, res); Set usedX = new HashSet<>(); Set usedY = new HashSet<>(); for (Integer j : res) { usedX.add(x[j]); usedY.add(y[j]); } int K = usedX.size() + usedY.size(); if (res.size() >= K) { ans = ans * twopow(K) % MOD; } else { ans = ans * ((twopow(K) - 1 + MOD) % MOD) % MOD; } } out.println(ans); } long twopow(int n) { if (n == 0) { return 1; } if (n % 2 == 0) { long t = twopow(n / 2); return t * t % MOD; } return twopow(n - 1) * 2 % MOD; } void dfs(int v, List res) { if (visited[v]) { return; } visited[v] = true; res.add(v); for (int j : edges.get(v)) { dfs(j, res); } } }