비밀 메시지

상근이는 창영이가 보낸 비밀 메시지를 받았다. 메시지는 알파벳 대문자로만 이루어져 있고, 길이는 2 이상이다.

메시지를 해독하려면 다음 연산을 수행해야 한다. 문자열 $S$의 앞에서부터 몇 글자를 지운 문자열, 또는 $S$의 뒤에서부터 몇 글자를 지운 문자열 가운데 하나를 조각으로 고른 뒤, 그 조각을 $S$의 앞이나 뒤에 붙인다. 지우는 글자 수는 1 이상이고 $S$의 길이보다 작아야 한다. 즉 조각은 비어 있지 않고, $S$ 전체와 같지도 않다.

예를 들어 문자열 ABC에 연산을 수행하는 방법은 모두 8가지이다.

• AABC (A + ABC)
• ABABC (AB + ABC)
• BCABC (BC + ABC)
• CABC (C + ABC)
• ABCA (ABC + A)
• ABCAB (ABC + AB)
• ABCBC (ABC + BC)
• ABCC (ABC + C)

상근이가 해독을 마친 문자열이 주어진다. 이 문자열을 만드는 방법의 수를 세는 프로그램을 작성한다. 연산은 여러 번 수행해도 된다. 만들어진 문자열이 같더라도 연산 과정이 다르면 서로 다른 방법으로 센다. 예를 들어 AA에서 AAA를 만드는 방법은 모두 4가지이다.

첫째 줄에 해독을 마친 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있고, 길이는 2 이상 100 이하이다.

첫째 줄에 주어진 문자열을 만드는 방법의 수를 출력한다. 처음 메시지의 길이는 2 이상이어야 한다. 방법의 수가 매우 커질 수 있으므로 2014로 나눈 나머지를 출력한다. 만들 수 없으면 0을 출력한다.

ABABA를 만드는 방법은 모두 8가지이다.

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