Circle

Μια ωραία καλοκαιρινή μέρα ενώ ο Mirko έπινε λεμονάδα στο δωμάτιό του...

"Μεγάλε αδερφέ!", φωνάζει ο Stanko.

"Αναρωτιέμαι μερικές φορές ποιος από τους δυο μας είναι ο μεγάλος. Τι είναι;", ρώτησε ο Mirko.

"Ακούσε προσεκτικά! Στην πίσω αυλή έχω ~N~ βότσαλα τοποθετημένα σε κύκλο. Μερικά από τα βότσαλα είναι μαύρα, μερικά είναι λευκά. Θα κάνω το εξής: ανάμεσα σε οποιαδήποτε δύο γειτονικά βότσαλα του ίδιου χρώματος θα βάλω ένα μαύρο βότσαλο και ανάμεσα σε δύο γειτονικά βότσαλα διαφορετικών χρωμάτων θα βάλω ένα λευκό βότσαλο. Σε εκείνο το σημείο θα υπάρχουν ~2N~ βότσαλα στον κύκλο, οπότε θα αφαιρέσω τα αρχικά ~N~ βότσαλα έτσι ώστε να μείνουν μόνο τα ~N~ βότσαλα που προστέθηκαν τελευταία. Και όλα αυτά σκοπεύω να τα κάνω ακριβώς ~\mathbf{K}~ φορές. Και μετά θα πρέπει να καθορίσεις τον αρχικό μου κύκλο", είπε ο Stanko επί μακρόν.

"Χα! Δεν θα πέσω θύμα του κόλπου σου! Μπορώ να δω ότι δεν είναι απαραίτητα δυνατό να γνωρίζουμε ακριβώς ποιος ήταν ο αρχικός κύκλος, αλλά μπορώ να αριθμήσω τους διακριτούς αρχικούς κύκλους που δίνουν το ίδιο αποτέλεσμα με τον κύκλο σου μετά ακριβώς από ~K~ από εκείνους τους περίεργους μετασχηματισμούς σου", απάντησε ο Mirko.

Σας δίνεται η διαμόρφωση του κύκλου πριν ο Stanko εκτελέσει τον μετασχηματισμό που περιγράφηκε πάνω, ~K~ φορές.

Γράψτε ένα πρόγραμμα που να καθορίζει τον αριθμό των διακριτών αρχικών κύκλων που δίνουν τον ίδιο κύκλο μετά από ~K~ μετασχηματισμούς όπως κάνει ο αρχικός κύκλος του Stanko μετά τους ~K~ μετασχηματισμούς.

Δύο διαμορφώσεις βότσαλων θεωρούνται ότι είναι ο ίδιος κύκλος εάν μπορεί να προκύψει η μία από την άλλη περιστρέφοντάς την οποιονδήποτε αριθμό θέσεων. Για παράδειγμα το BBW και το BWB είναι ο ίδιος κύκλος ενώ το BBWWBW και το WWBBWB δεν είναι.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους ~N~ και ~K, 3 \le N \le 100,\,1 \le K \le 10~, όπου ~N~ είναι ο αριθμός των βότσαλων στον κύκλο και ~K~ είναι ο αριθμός των μετασχηματισμών που έκανε ο Stanko.

Η δεύτερη γραμμή περιέχει ακριβώς ~N~ χαρακτήρες 'B' ή 'W' που αντιπροσωπεύουν τον αρχικό κύκλο του Stanko.

Έξοδος

Τυπώστε τον αριθμό των πιθανών διακριτών αρχικών κύκλων σε μία μόνο γραμμή.

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

input

3 1
BBW

output

2

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

Οι κύκλοι BBW και WBW γίνονται κύκλος BWW μετά από έναν μετασχηματισμό.

input

6 2
WBWWBW

output

3