## CCO '14 P3 - Werewolf

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
##### Canadian Computing Competition: 2014 Stage 2, Day 1, Problem 3

As they usually do, robots are playing the game of Werewolf, and the robots are numbered with integers from to . Exactly of these robots are werewolves, and the remainder are civilians. Though the game of Werewolf involves various aspects, we will focus on a single discussion phase of the game.

Robots accuse other robots of being werewolves and defend other robots by vouching for their innocence.

The werewolves know each other's identities and:

• A werewolf never accuses another werewolf;
• Any robot that a werewolf defends is another werewolf.

Civilians may accuse or defend either type of robot.

• No robot is both accused and defended.
• No robot is accused or defended more than once.
• For a robot to accuse or defend a robot , then .

You will be given all the accusations and defenses between robots where there are exactly werewolves. A role assignment identifies each of the robots as either werewolf or civilian. Your goal is to figure out how many role assignments satisfy all the above constraints.

#### Input Specification

The first line contains three numbers (each separated by one space):

• , the number of robots, followed by
• , the number of werewolves, followed by
• , the number of accusations/defenses.

The next lines give the accusations and defenses. Each of these lines will be one of the following two forms:

• indicates that robot accused robot of being a werewolf;
• indicates that robot defended robot .

You may assume that for 20% of the marks for this problem, .

#### Output Specification

Output the number of role assignments that are consistent with the given information. Since this number may be very large, you must output this answer modulo .

#### Sample Input 1

2 1 1
D 1 2

#### Output for Sample Input 1

1

#### Explanation of Output for Sample Input 1

If robot is a werewolf, then robot must also be, which is too many werewolves! The only possibility is that robot is the sole werewolf.

#### Sample Input 2

2 1 0

#### Output for Sample Input 2

2

#### Explanation of Output for Sample Input 2

With no information, either robot or robot could have been a werewolf.

#### Sample Input 3

3 2 2
A 1 2
D 1 3

#### Output for Sample Input 3

2

#### Explanation of Output for Sample Input 3

Either robot is a werewolf, which implies robot is a civilian and robot is a werewolf as well, or robot is a civilian (which allows robot and to both be werewolves).

• commented on Feb. 9, 2020, 8:52 p.m. edited

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on March 23, 2018, 10:56 a.m.

Output specification

you must output this answer "module" 109+7

Do you mean modulo?

• commented on March 23, 2018, 6:22 p.m.

Fixed. Thank you for pointing that out!

• commented on March 12, 2015, 5:06 p.m.

Sample input 2 is missing and explanation of sample input 1

• commented on March 12, 2015, 7:32 p.m.

Fixed.