WC '18 Finals S3 - Screen Time

View as PDF

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 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 ) 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 possible equal-length scenes to include in the script, each of which involves exactly two of the three actors in question. The -th scene features the two actors and . The Head Monkey may select any non-empty subset of these scenes to include (note that there are such possible subsets).

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

In test cases worth of the points, .
In test cases worth another of the points, .
In test cases worth another of the points, .

Input Specification

The first line of input consists of a single integer, .
lines follow, the -th of which consists of two space-separated integers, and , for .

Output Specification

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

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 is chosen, then while , making this a valid subset. Subsets and are also valid. Therefore, the answer is .