Secret Code

Ο Γιάννης ο αγρότης έχει ένα μυστικό μήνυμα που θέλει να κρύψει από τις αγελάδες του. Το μήνυμα είναι μια συμβολοσειρά μήκους τουλάχιστον ~2~ που περιέχει μόνο τους χαρακτήρες ~A..Z~.

Για να κρυπτογραφήσει το μήνυμά του, ο Γιάννης εφαρμόζει μια ακολουθία "διαδικασιών" σε αυτό, όπου μια διαδικασία που εφαρμόζεται σε μια συμβολοσειρά ~S~ πρώτα συντομεύει την ~S~ αφαιρώντας είτε τον πρώτο είτε τον τελευταίο χαρακτήρα της, και στη συνέχεια η αρχική συμβολοσειρά ~S~ προστίθεται είτε στην αρχή είτε στο τέλος. Για παράδειγμα, μια μόνο διαδικασία στη συμβολοσειρά ~ABCD~ θα μπορούσε να έχει ως αποτέλεσμα τέσσερις πιθανές συμβολοσειρές:

~BCDABCD~
~ABCABCD~
~ABCDABC~
~ABCDBCD~

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

Είσοδος

• Γραμμή ~1~: Μια συμβολοσειρά μήκους το πολύ ~100~.

Έξοδος

• Γραμμή ~1~: Ο αριθμός των διαφορετικών τρόπων με τους οποίους ο Γιάννης θα μπορούσε να έχει παραγάγει αυτή τη συμβολοσειρά εφαρμόζοντας μία ή περισσότερες διαδοχικές διαδικασίες σε κάποια αρχική συμβολοσειρά μήκους τουλάχιστον ~2~. Αν δεν υπάρχουν τέτοιοι τρόποι, εκτυπώστε ένα μηδενικό.

Παράδειγμα

input (scode.in)

ABABA

output (scode.out)

6

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

Ακολουθούν οι διαφορετικοί τρόποι με τους οποίους ο Γιάννης θα μπορούσε να έχει παραγάγει το ~ABABA~:

1. Ξεκινήστε με το ~ABA \to AB+ABA~
2. Ξεκινήστε με το ~ABA \to ABA+BA~
3. Ξεκινήστε με το ~AB \to AB+A \to AB+ABA~
4. Ξεκινήστε με το ~AB \to AB+A \to ABA+BA~
5. Ξεκινήστε με το ~BA \to A+BA \to AB+ABA~
6. Ξεκινήστε με το ~BA \to A+BA \to ABA+BA~