Werewolf

This problem is translated from CCO 2014 Day1 T3 "Werewolf".

There are \(N\) robots playing a werewolf game, numbered from \(1\) to \(N\). Exactly \(W\) of these robots are werewolves, and the rest are citizens. Some robots accuse or protect each other according to the following rules:

• If a werewolf robot accuses another robot then that other robot must be a citizen. (That is, a werewolf never accuses a fellow werewolf.)
• If a werewolf robot protects another robot then that other robot must be a werewolf.
• Citizens have no restrictions and may accuse or protect any robot.

Additional conditions hold:

• No robot is both accused and protected.
• No robot is accused or protected more than once.
• If robot \(A\) accuses or protects robot \(B\), then \(A < B\) (i.e. the source robot has a smaller number than the target robot).

You are given all the accusation and protection relations among the \(N\) robots together with the number \(W\) of werewolves. Your task is to count the number of role assignments that satisfy all these conditions while having exactly \(W\) werewolves.

inputFormat

The first line contains three integers \(N\), \(W\), and \(M\), where \(N\) is the total number of robots, \(W\) is the number of werewolves, and \(M\) is the number of relations.

Each of the following \(M\) lines contains a relation in the format:

A C B

Here, A and B are robot numbers with \(A < B\), and C is a character that is either A (for an accusation) or P (for protection).

outputFormat

Output a single integer representing the number of valid role assignments satisfying the constraints, with exactly \(W\) werewolves.

sample

5 2 2
1 A 3
2 P 5

3