WC '18 Finals S3 - Screen Time

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.5s
Memory limit: 64M

Author:
Problem type
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.


Comments

There are no comments at the moment.