Woburn Challenge 2018-19 Finals Round - Senior Division

A trio of rival actors, numbered $1\dots 3$ from oldest to youngest, are set to make appearances in the cows' and monkeys' film. However, their contracts state that the oldest of them (actor $1$) must receive more screen time than either one of the others! The Head Monkey may need to adjust her script to ensure that that's the case.

There are $N$ $(1\le N\le 200000)$ possible equal-length scenes to include in the script, each of which involves exactly two of the three actors in question. The $i$-th scene features the two actors $A_i$ and $B_i$ $(1\le A_i,B_i\le 3,A_i\ne B_i)$. The Head Monkey may select any non-empty subset of these $N$ scenes to include (note that there are $2^N-1$ such possible subsets).

Letting $S_i$ be the number of scenes featuring actor $i$, how many different subsets of scenes could the Head Monkey choose to include such that both $S_1>S_2$ and $S_1>S_3$ hold? As there may be many valid subsets, you only need to compute the number of them modulo $1000000007$.

Subtasks

In test cases worth $24\mathrm{\%}$ of the points, $N\le 20$.
In test cases worth another $18\mathrm{\%}$ of the points, $N\le 200$.
In test cases worth another $18\mathrm{\%}$ of the points, $N\le 3000$.

Input Specification

The first line of input consists of a single integer, $N$.
$N$ lines follow, the $i$-th of which consists of two space-separated integers, $A_i$ and $B_i$, for $i=1\dots N$.

Output Specification

Output a single integer, the number of valid subsets of scenes (modulo $1000000007$).

Sample Input 1

5
3 1
1 2
3 2
2 3
3 1

Sample Output 1

3

Sample Input 2

15
3 2
1 2
3 1
2 1
2 1
2 3
1 3
3 2
1 2
1 3
2 3
3 1
1 3
2 3
2 1

Sample Output 2

7266

Sample Explanation

In the first case, if the subset of scenes $\{1,2\}$ is chosen, then $S_1=2$ while $S_2=S_3=1$, making this a valid subset. Subsets $\{1,2,5\}$ and $\{2,5\}$ are also valid. Therefore, the answer is $3mod1000000007=3$.