### 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`(1 ≤

_{i}`A`,

_{i}`B`≤ 3,

_{i}`A`≠

_{i}`B`). The Head Monkey may select any non-empty subset of these

_{i}`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 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`, for

_{i}`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`_{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 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)

It's quiet in here...