Walking on a Graph

Υπάρχει ένας γράφος με ~N~ κόμβους, αριθμημένους από το ~1~ έως το ~N~. Κάθε κόμβος είναι χρωματισμένος είτε μαύρος είτε λευκός. Επιπλέον, είναι γνωστό ότι ο κόμβος ~1~ είναι μαύρος και ο κόμβος ~2~ είναι λευκός. Για κάθε ~i~ και ~j~ με ~i \ne j~, υπάρχει μια κατευθυνόμενη ακμή από τον κόμβο ~i~ προς τον κόμβο ~j~, η οποία είναι είτε κόκκινη είτε μπλε. Το χρώμα της καθορίζεται με βάση τους ακόλουθους κανόνες:

• Αν ~i < j~ και οι κόμβοι έχουν το ίδιο χρώμα, τότε η ακμή είναι κόκκινη.
• Αν ~i < j~ και οι κόμβοι έχουν διαφορετικά χρώματα, τότε η ακμή είναι μπλε.
• Αν ~i > j~ και οι κόμβοι έχουν το ίδιο χρώμα, τότε η ακμή είναι μπλε.
• Αν ~i > j~ και οι κόμβοι έχουν διαφορετικά χρώματα, τότε η ακμή είναι κόκκινη.

Το αγαπημένο χρώμα του LoBren είναι αρχικά το μπλε. Στη συνέχεια, κάνει μια διαδρομή στον γράφο (σημειώστε ότι οι διαδρομές επιτρέπεται να περιέχουν επαναλαμβανόμενες κορυφές και ακμές). Ακολουθεί τους παρακάτω κανόνες κατά τη μετακίνησή του:

• Αν βρίσκεται αυτή τη στιγμή στον κόμβο ~1~, το αγαπημένο του χρώμα γίνεται μπλε.
• Διαφορετικά, αν βρίσκεται αυτή τη στιγμή στον κόμβο ~2~, το αγαπημένο του χρώμα γίνεται κόκκινο.
• Στη συνέχεια, διασχίζει μια εξερχόμενη ακμή από τον τρέχοντα κόμβο, η οποία έχει το ίδιο χρώμα με το αγαπημένο του χρώμα. Μπορεί να αποδειχθεί ότι μια τέτοια ακμή υπάρχει πάντα.
• Τέλος, μπορεί προαιρετικά να επαναλάβει τη διαδικασία.

Καταγράφοντας τους κόμβους που επισκέπτεται, με τη σειρά που τους επισκέπτεται, προκύπτει μια λίστα ~l_1,\ l_2,\ ...,\ l_L~. Βρείτε το πλήθος των δυνατών λιστών, modulo ~10^9+7~, που ικανοποιούν τις ακόλουθες συνθήκες:

• Η λίστα ξεκινά από τον κόμβο ~1~ και τελειώνει στον κόμβο ~2~.
• Για κάθε ~i~ με ~3 \le i \le N~, ο κόμβος ~i~ εμφανίζεται το πολύ μία φορά στη λίστα.
• Για κάθε ~j~ με ~3 \le j \le L~, ισχύει ~l_{j-2} \ne l_j~.

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

Μπορεί επίσης να είναι χρήσιμο να σημειωθεί ότι το «mod» αντιστοιχεί στον τελεστή % στις περισσότερες γλώσσες προγραμματισμού και δηλώνει το υπόλοιπο της διαίρεσης. Για παράδειγμα, ~5 \bmod 3=2~ και ~17 \bmod 4=1~.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει έναν ακέραιο αριθμό ~N~.

Η επόμενη γραμμή θα περιέχει μια συμβολοσειρά μήκους ~N~, αποτελούμενη από τους χαρακτήρες B και W. Αν ο ~i~-οστός χαρακτήρας είναι B, τότε ο κόμβος ~i~ είναι μαύρος. Διαφορετικά, είναι λευκός. Είναι εγγυημένο ότι ο κόμβος ~1~ είναι μαύρος και ο κόμβος ~2~ είναι λευκός.

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι ~25~ διαθέσιμοι βαθμοί:

Βαθμοί	Όρια του ~N~	Περιορισμοί
~1~	~3 \le N \le 8~	Κανένας επιπλέον περιορισμός.
~3~	~3 \le N \le 20~	Κανένας επιπλέον περιορισμός.
~4~	~3 \le N \le 50~	Υπάρχει ακριβώς ένας μαύρος κόμβος.
~4~	~3 \le N \le 50~	Υπάρχει ένας ακέραιος ~i~ με ~2 \le i \le N~, τέτοιος ώστε όλοι οι κόμβοι στο διάστημα ~[2,i]~ να είναι λευκοί και όλοι οι υπόλοιποι κόμβοι να είναι μαύροι.
~6~	~3 \le N \le 50~	Υπάρχουν το πολύ 5 μαύροι κόμβοι.
~7~	~3 \le N \le 50~	Κανένας επιπλέον περιορισμός.

Έξοδος

Σε μία γραμμή, εκτυπώστε το πλήθος των δυνατών λιστών, modulo ~10^9+7~.

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

input

4
BWWB

output

4

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

Ο γράφος έχει την ακόλουθη μορφή:

Οι συνεχείς γραμμές αντιπροσωπεύουν τις μπλε ακμές, ενώ οι διακεκομμένες γραμμές αντιπροσωπεύουν τις κόκκινες ακμές. Οι δυνατές διαδρομές είναι:

• ~1 \rightarrow \underline{2}~
• ~1 \rightarrow 3 \rightarrow \underline{2}~
• ~1 \rightarrow 3 \rightarrow 4 \rightarrow \underline{2}~
• ~1 \rightarrow \underline{2} \rightarrow \underline{3} \rightarrow 1 \rightarrow \underline{2}~

Το αγαπημένο χρώμα είναι κόκκινο στους υπογραμμισμένους κόμβους και μπλε στους υπόλοιπους.

input

12
BWBWBBBWWBBW

output

3377552