Farmer John רוצה להסתיר מהפרות מסר: מחרוזת באורך לפחות 2, המכילה רק A..Z.

הוא מצפין בסדרת פעולות. פעולה על $S$ מסירה חלק, אך לא את כל, התווים מההתחלה או מהסוף של $S$, ואז מצרפת את המחרוזת המקורית $S$ לתחילת או לסוף השארית. פעולה אחת על ABC יכולה לתת שמונה מחרוזות:

AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC

בהינתן המחרוזת המוצפנת הסופית, ספרו את הדרכים ליצור אותה בפעולה אחת או יותר ממחרוזת מקור כלשהי. הפעולות שונות גם אם ההצפנה זהה. למשל יש ארבע דרכים שונות לקבל AAA מ־AA.

הדפיסו את התשובה מודולו 2014.

קלט

• שורה 1: מחרוזת מוצפנת באורך לכל היותר 100.

פלט

• שורה 1: מספר הדרכים ליצור אותה בפעולה אחת או יותר ברצף ממחרוזת התחלתית באורך לפחות 2, מודולו 2014. אם אין דרכים, הדפיסו אפס.

דוגמאות

קלט 1

ABABA

פלט 1

8

הסבר

אלה הדרכים ליצור ABABA:

1. מחרוזת התחלתית: ABA -> AB+ABA
2. מחרוזת התחלתית: ABA -> ABA+BA
3. מחרוזת התחלתית: AB -> AB+A -> AB+ABA
4. מחרוזת התחלתית: AB -> AB+A -> ABA+BA
5. מחרוזת התחלתית: BA -> A+BA -> AB+ABA
6. מחרוזת התחלתית: BA -> A+BA -> ABA+BA
7. מחרוזת התחלתית: ABAB -> ABAB+A
8. מחרוזת התחלתית: BABA -> A+BABA

מחברי הבעיה: Brian Dean ו־Lewin Gan