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 200\,000)~ 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 ~1\,000\,000\,007~.

Subtasks

In test cases worth ~24\%~ of the points, ~N \le 20~.
In test cases worth another ~18\%~ of the points, ~N \le 200~.
In test cases worth another ~18\%~ of the points, ~N \le 3\,000~.

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 ~1\,000\,000\,007~).

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 ~3 \bmod 1\,000\,000\,007 = 3~.