Farmer John은 소들에게 숨기고 싶은 메시지가 있다. 길이가 최소 2이고 A..Z만 포함하는 문자열이다.

암호화는 연속 작업을 적용한다. 문자열 $S$에서 앞쪽 일부 (전부는 아님) 또는 뒤쪽 일부 (전부는 아님)를 지워 $S$를 줄인 뒤 원래 문자열 $S$를 남은 것의 앞 또는 뒤에 붙인다. ABC에 한 번 적용하면 다음 여덟 문자열이 가능하다.

AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC

최종 암호 문자열이 주어질 때 어떤 원본 문자열에서 한 번 이상의 작업으로 생성한 방법 수를 구하라. 같은 암호 결과여도 작업은 다르게 센다. 예를 들어 AA에서 AAA를 얻는 네 가지 다른 방법이 있다.

답을 2014로 나눈 나머지를 출력하라.

입력

• 1번 줄: 길이가 최대 100인 암호 문자열.

출력

• 1번 줄: 길이가 최소 2인 어떤 원본에서 한 번 이상의 연속 작업으로 문자열을 만드는 방법 수를 2014로 나눈 나머지. 방법이 없으면 0.

예제

입력 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