Werewolf

Όπως κάνουν συνήθως, ~N~ ρομπότ παίζουν το παιχνίδι του Λυκανθρώπου και τα ρομπότ είναι αριθμημένα με ακέραιους από το ~1~ έως το ~N~. Ακριβώς ~W~ από αυτά τα ρομπότ είναι λυκάνθρωποι, και τα υπόλοιπα είναι πολίτες. Αν και το παιχνίδι του Λυκάνθρωπου περιλαμβάνει διάφορες πτυχές, θα επικεντρωθούμε σε μια φάση συζήτησης του παιχνιδιού.

Τα ρομπότ κατηγορούν άλλα ρομπότ ότι είναι λυκάνθρωποι και υπερασπίζονται άλλα ρομπότ με την μαρτυρία τους για την αθωότητά τους.

Οι λυκάνθρωποι γνωρίζουν τις ταυτότητες του άλλου και:

• Ένας λυκάνθρωπος δεν κατηγορεί ποτέ άλλο λυκάνθρωπο.

• Οποιοδήποτε ρομπότ που υπερασπίζεται ένας λυκάνθρωπος είναι ένας άλλος λυκάνθρωπος.

Οι πολίτες μπορούν να κατηγορήσουν ή να υπερασπιστούν κάθε τύπο ρομπότ.

Οι πρόσθετοι περιορισμοί καθιστούν το καθήκον μας λίγο πιο εύκολο:

• Κανένα ρομπότ δεν κατηγορείται και υπερασπίζεται ταυτόχρονα.

• Κανένα ρομπότ δεν κατηγορείται ή υπερασπίζεται περισσότερες από μία φορές.

• Για ένα ρομπότ ~A~ να κατηγορήσει ή να υπερασπιστεί το ρομπότ ~B~, τότε ~A < B~.

Θα σας δοθούν όλες οι κατηγορίες και οι υπερασπίσεις μεταξύ των ρομπότ ~N~ όπου υπάρχουν ακριβώς ~W~ λυκάνθρωποι. Μια ανάθεση ρόλου προσδιορίζει κάθε ένα από τα ρομπότ είτε ως λυκάνθρωπο είτε ως πολίτη. Ο σκοπός σας είναι να καταλάβουμε πόσες αναθέσεις ρόλων ικανοποιούν όλους τους παραπάνω περιορισμούς.

Είσοδος

Η πρώτη γραμμή περιέχει τρεις αριθμούς (χωρισμένοι με ένα κενό):

• ~N~ (~1 \le N \le 200~), τον αριθμό των ρομπότ, ακολουθούμενο από

• ~W~ (~0 \le W \le N~), τον αριθμό των λυκανθρώπων, ακολουθούμενο από

• ~M~ (~0 \le M < N~), τον αριθμό των κατηγοριών/υπερασπίσεων.

Οι επόμενες ~M~ γραμμές δίνουν τις κατηγορίες και τις υπερασπίσεις. Καθεμία από αυτές τις γραμμές θα είναι μιας από τις ακόλουθες δύο μορφές:

• ~A~ ~a~ ~b~ υποδεικνύει ότι το ρομπότ ~a~ κατηγόρησε το ρομπότ ~b~ ότι είναι λυκάνθρωπος

• ~D~ ~a~ ~b~ υποδεικνύει ότι το ρομπότ ~a~ υπερασπίστηκε το ρομπότ ~b~.

Μπορείτε να υποθέσετε ότι για το 20% της βαθμολογίας του προβλήματος, ~N \le 20~.

Έξοδος

Εκτυπώστε τον αριθμό των αναθέσεων ρόλων που είναι συνεπή με τις δεδομένες πληροφορίες. Μιας και αυτός ο αριθμός μπορεί να είναι πολύ μεγάλος, πρέπει να εκτυπώσετε την απάντηση ως υπόλοιπο ακέραιας διαίρεσης (modulo) με το ~10^9 + 7~.

Παραδείγματα

input

2 1 1
D 1 2

output

1

Επεξήγηση του πρώτου παραδείγματος

Αν το ρομπότ ~1~ είναι ένας λυκάνθρωπος, τότε το ρομπότ ~2~ πρέπει να είναι και αυτό λυκάνθρωπος, που θα είναι πολλοί λυκάνθρωποι! Η μόνη πιθανότητα είναι ότι το ρομπότ ~2~ είναι ο μόνος λυκάνθρωπος.

input

2 1 0

output

2

Επεξήγηση του δεύτερου παραδείγματος

Χωρίς καμία πληροφορία, ούτε το ρομπότ ~1~ ούτε το ρομπότ ~2~ θα μπορούσε να είναι λυκάνθρωπος.

input

3 2 2
A 1 2
D 1 3

output

2

Επεξήγηση του τρίτου παραδείγματος

Είτε το ρομπότ ~1~ είναι λυκάνθρωπος, που υπονοεί ότι το ρομπότ ~2~ είναι πολίτης και το ρομπότ ~3~ είναι επίσης λυκάνθρωπος, είτε το ρομπότ ~1~ είναι πολίτης (που επιτρέπει το ρομπότ ~2~ και ~3~ να είναι λυκάνθρωποι).