Breed Assignment

Ο Γιάννης ο αγρότης έχει ~N~ αγελάδες ~(2 \le N \le 15)~ που η καθεμία ανήκει σε μια από τρεις διαφορετικές ράτσες: Χολστάιν, Τζέρσεϊ ή Γκερνσεϊ.

Δυστυχώς, ο Γιάννης δεν μπορεί να θυμηθεί τις ακριβείς ράτσες των αγελάδων του! Θυμάται, όμως, μια λίστα με ~K\;(1 \le K \le 50)~ σχέσεις μεταξύ ζευγών αγελάδων του. Για παράδειγμα, μπορεί να θυμάται ότι οι αγελάδες ~1~ και ~2~ είναι της ίδιας ράτσας, ή ότι οι αγελάδες ~1~ και ~5~ είναι διαφορετικής ράτσας.

Δεδομένης της λίστας του Γιάννη με τις σχέσεις μεταξύ ζευγών αγελάδων, βοηθήστε τον να υπολογίσει τον αριθμό των διαφορετικών δυνατών κατανομών σε ράτσες των αγελάδων του (αυτός ο αριθμός μπορεί να είναι μηδέν αν η λίστα του περιέχει αντιφατικές πληροφορίες).

Είσοδος

• Γραμμή ~1~: Δύο ακέραιοι αριθμοί χωρισμένοι με ένα κενό: ~N~ και ~K~.

• Γραμμές ~2..1+K~: Κάθε γραμμή περιγράφει τη σχέση μεταξύ ενός ζεύγους αγελάδων ~x~ και ~y~ ~(1 \le x,y \le N,\; x != y)~. Είναι είτε της μορφής "~S\;x\;y~", που σημαίνει ότι οι ~x~ και ~y~ είναι της ίδιας ράτσας, είτε της μορφής "~D\;x\;y~", που σημαίνει ότι οι ~x~ και ~y~ είναι διαφορετικής ράτσας.

Έξοδος

• Γραμμή ~1~: Ο αριθμός των δυνατών κατανομών σε ράτσες.

Παράδειγμα

input (assign.in)

4 2
S 1 2
D 1 3

output (assign.out)

18

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

Υπάρχουν ~4~ αγελάδες. Οι αγελάδες ~1~ και ~2~ είναι της ίδιας ράτσας, και οι αγελάδες ~1~ και ~3~ είναι διαφορετικής ράτσας. Οι ακόλουθες έξι κατανομές σε ράτσες είναι πιθανές για τις πρώτες ~3~ αγελάδες: ~HHG~, ~HHJ~, ~GGH~, ~GGJ~, ~JJH~, ~JJG~. Για κάθε μία από αυτές, μπορούμε να έχουμε ~3~ πιθανές κατανομές ράτσας για την ~4~η αγελάδα, που δίνει συνολικά ~18~ διαφορετικές κατανομές που είναι συμβατές με τη λίστα του Γιάννη.