Woburn Challenge 2018-19 Finals Round - Senior Division

Problem 3: Screen Time

A trio of rival actors, numbered 1..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 ≤ N ≤ 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 ≤ A_i, B_i ≤ 3, A_i ≠ 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₁ > S₂ and S₁ > S₃ 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 4/17 of the points, N ≤ 20.
In test cases worth another 3/17 of the points, N ≤ 200.
In test cases worth another 3/17 of the points, N ≤ 3000.

Input Format

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..N.

Output Format

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₁ = 2 while S₂ = S₃ = 1, making this a valid subset. Subsets (1, 2, 5) and (2, 5) are also valid. Therefore, the answer is 3 modulo 1,000,000,007 = 3.

All Submissions
Best Solutions

Point Value: 14 (partial)
Time Limit: 5.00s
Memory Limit: 64M
Added: May 18, 2019
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)