시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 21 11 11 61.111%

문제

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

메시지를 해독하려면 메시지에 연산을 수행해야 한다. 연산을 하려면 문자열 S에 S의 일부(전부는 안됨) 문자를 앞에서부터 지운 문자열 또는 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가지가 있다.

입력

첫째 줄에 해독 완료한 문자열이 주어진다. 길이는 100을 넘지 않는다.

출력

첫째 줄에 입력으로 주어진 문자열을 만드는 방법의 수를 출력한다. 처음 문자열의 길이는 2보다 크거나 같아야 한다. 방법의 수가 매우 커질 수 있기 때문에, 2014로 나눈 나머지를 출력한다. 만약, 불가능한 경우에는 0을 출력한다.

예제 입력

ABABA

예제 출력

8

힌트

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

출처

Olympiad > USA Computing Olympiad > 2013-2014 Season > USACO February 2014 Contest > Silver 3번