시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 33 18 18 60.000%

문제

상근이는 창영이가 보낸 비밀 메시지를 받았다. 메시지는 알파벳 대문자로만 이루어져 있으며, 길이는 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을 출력한다.

예제 입력 1

ABABA

예제 출력 1

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
W3sicHJvYmxlbV9pZCI6Ijk5OTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNDRcdWJjMDAgXHViYTU0XHVjMmRjXHVjOWMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjYzNkXHVjNjAxXHVjNzc0XHVhYzAwIFx1YmNmNFx1YjBiOCBcdWJlNDRcdWJjMDAgXHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1YmMxYlx1YzU1OFx1YjJlNC4gXHViYTU0XHVjMmRjXHVjOWMwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZTM4XHVjNzc0XHViMjk0IDJcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1ZDU3NFx1YjNjNVx1ZDU1OFx1YjgyNFx1YmE3NCBcdWJhNTRcdWMyZGNcdWM5YzBcdWM1ZDAgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWQ1NThcdWI4MjRcdWJhNzQgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWM1ZDAgU1x1Yzc1OCBcdWM3N2NcdWJkODAoXHVjODA0XHViZDgwXHViMjk0IFx1YzU0OFx1YjQyOCkgXHViYjM4XHVjNzkwXHViOTdjIFx1YzU1ZVx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBcdWM5YzBcdWM2YjQgXHViYjM4XHVjNzkwXHVjNWY0IFx1YjYxMFx1YjI5NCBTXHVjNzU4IFx1Yzc3Y1x1YmQ4MChcdWM4MDRcdWJkODBcdWIyOTQgXHVjNTQ4XHViNDI4KSBcdWJiMzhcdWM3OTBcdWI5N2MgXHViNGE0XHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIFx1YzljMFx1YzZiNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgU1x1Yzc1OCBcdWM1NWVcdWM3NzRcdWIwOTggXHViNGE0XHVjNWQwIFx1YmQ5OVx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YmIzOFx1Yzc5MFx1YzVmNCBBQkNcdWM1ZDAgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWNkMWQgOFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QUFCQyAoQSArIEFCQyk8XC9saT5cclxuXHQ8bGk+QUJBQkMgKEFCICsgQUJDKTxcL2xpPlxyXG5cdDxsaT5CQ0FCQyAoQkMgKyBBQkMpPFwvbGk+XHJcblx0PGxpPkNBQkMgKEMgKyBBQkMpPFwvbGk+XHJcblx0PGxpPkFCQ0EgKEFCQyArIEEpPFwvbGk+XHJcblx0PGxpPkFCQ0FCIChBQkMgKyBBQik8XC9saT5cclxuXHQ8bGk+QUJDQkMgKEFCQyArIEJDKTxcL2xpPlxyXG5cdDxsaT5BQkNDIChBQkMgKyBDKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWQ1NzRcdWIzYzVcdWM3NDQgXHVjNjQ0XHViOGNjXHVkNTVjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNWYwXHVjMGIwXHVjNzQwIFx1YzVlY1x1YjdlYyBcdWJjODggXHVjMjE4XHVkNTg5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YjRlMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVhYzE5XHViMzU0XHViNzdjXHViM2M0LCBcdWM1ZjBcdWMwYjBcdWM3NTggXHViYzI5XHViYzk1XHVjNzc0IFx1YjJlNFx1Yjk3NFx1YjJlNFx1YmE3NCBcdWIyZTRcdWI5NzggXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1Y2U1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgQUFcdWM1ZDBcdWMxMWMgQUFBXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjZDFkIDRcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NzRcdWIzYzUgXHVjNjQ0XHViOGNjXHVkNTVjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWUzOFx1Yzc3NFx1YjI5NCAxMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjYzk4XHVjNzRjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMlx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1YWMwMCBcdWI5ZTRcdWM2YjAgXHVjZWU0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCAyMDE0XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPkFCQUJBXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjZDFkIDhcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkFCQVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTEgLSZndDsgQUIgKyBBQkE8XC9saT5cclxuXHQ8bGk+QUJBXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MSAtJmd0OyBBQkEgKyBCQTxcL2xpPlxyXG5cdDxsaT5BQlx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTEgLSZndDsgQUIgKyBBIC0mZ3Q7IEFCICsgQUJBPFwvbGk+XHJcblx0PGxpPkFCXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MSAtJmd0OyBBQiArIEEgLSZndDsgQUJBICsgQkE8XC9saT5cclxuXHQ8bGk+QkFcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxIC0mZ3Q7IEEgKyBCQSAtJmd0OyBBQiArIEFCQTxcL2xpPlxyXG5cdDxsaT5CQVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTEgLSZndDsgQSArIEJBIC0mZ3Q7IEFCQSArIEJBPFwvbGk+XHJcblx0PGxpPkFCQUJcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxIC0mZ3Q7IEFCQUIgKyBBPFwvbGk+XHJcblx0PGxpPkJBQkFcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxIC0mZ3Q7IEEgKyBCQUJBPFwvbGk+XHJcbjxcL29sPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk5OTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTZWNyZXQgQ29kZSIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaGFzIHNlY3JldCBtZXNzYWdlIHRoYXQgaGUgd2FudHMgdG8gaGlkZSBmcm9tIGhpcyBjb3dzOyB0aGUgbWVzc2FnZSBpcyBhIHN0cmluZyBvZiBsZW5ndGggYXQgbGVhc3QgMiBjb250YWluaW5nIG9ubHkgdGhlIGNoYXJhY3RlcnMgQS4uWi48XC9wPlxyXG5cclxuPHA+VG8gZW5jcnlwdCBoaXMgbWVzc2FnZSwgRkogYXBwbGllcyBhIHNlcXVlbmNlIG9mICZxdW90O29wZXJhdGlvbnMmcXVvdDsgdG8gaXQsIHdoZXJlIGFuIG9wZXJhdGlvbiBhcHBsaWVkIHRvIGEgc3RyaW5nIFMgZmlyc3Qgc2hvcnRlbnMgUyBieSByZW1vdmluZyBlaXRoZXIgc29tZSAoYnV0IG5vdCBhbGwpIG9mIHRoZSBpbml0aWFsIGNoYXJhY3RlcnMgb3Igc29tZSAoYnV0IG5vdCBhbGwpIG9mIHRoZSBmaW5hbCBjaGFyYWN0ZXJzIGZyb20gUywgYWZ0ZXIgd2hpY2ggdGhlIG9yaWdpbmFsIHN0cmluZyBTIGlzIGF0dGFjaGVkIGVpdGhlciBhdCB0aGUgYmVnaW5uaW5nIG9yIGVuZC4gJm5ic3A7Rm9yIGV4YW1wbGUsIGEgc2luZ2xlIG9wZXJhdGlvbiB0byB0aGUgc3RyaW5nIEFCQyBjb3VsZCByZXN1bHQgaW4gZWlnaHQgcG9zc2libGUgc3RyaW5nczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BQUJDPFwvbGk+XHJcblx0PGxpPkFCQUJDPFwvbGk+XHJcblx0PGxpPkJDQUJDPFwvbGk+XHJcblx0PGxpPkNBQkM8XC9saT5cclxuXHQ8bGk+QUJDQTxcL2xpPlxyXG5cdDxsaT5BQkNBQjxcL2xpPlxyXG5cdDxsaT5BQkNCQzxcL2xpPlxyXG5cdDxsaT5BQkNDPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGZpbmFsIGVuY3J5cHRlZCBzdHJpbmcsIHBsZWFzZSBjb3VudCB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIHdheXMgRkogY291bGQgaGF2ZSBwcm9kdWNlZCB0aGlzIHN0cmluZyB1c2luZyBvbmUgb3IgbW9yZSByZXBlYXRlZCBvcGVyYXRpb25zIGFwcGxpZWQgdG8gc29tZSBzb3VyY2Ugc3RyaW5nLiAmbmJzcDtPcGVyYXRpb25zIGFyZSB0cmVhdGVkIGFzIGJlaW5nIGRpc3RpbmN0IGV2ZW4gaWYgdGhleSBnaXZlIHRoZSBzYW1lIGVuY3J5cHRpb24gb2YgRkomIzM5O3MgbWVzc2FnZS4gJm5ic3A7Rm9yIGV4YW1wbGUsIHRoZXJlIGFyZSBmb3VyIGRpc3RpbmN0IHNlcGFyYXRlIHdheXMgdG8gb2J0YWluIEFBQSBmcm9tIEFBLjxcL3A+XHJcblxyXG48cD5QcmludCB5b3VyIGFuc3dlciBvdXQgbW9kdWxvIDIwMTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogQSBzaW5nbGUgZW5jcnlwdGVkIHN0cmluZyBvZiBsZW5ndGggYXQgbW9zdCAxMDAuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBUaGUgbnVtYmVyIG9mIHdheXMgRkogY291bGQgaGF2ZSBwcm9kdWNlZCB0aGlzIHN0cmluZyB3aXRoIG9uZSBvciBtb3JlIHN1Y2Nlc3NpdmUgb3BlcmF0aW9ucyBhcHBsaWVkIHRvIHNvbWUgaW5pdGlhbCBzdHJpbmcgb2YgbGVuZ3RoIGF0IGxlYXN0IDIsIHdyaXR0ZW4gb3V0IG1vZHVsbyAyMDE0LiAmbmJzcDtJZiB0aGVyZSBhcmUgbm8gc3VjaCB3YXlzLCBvdXRwdXQgemVyby48XC9wPlxyXG4iLCJoaW50IjoiPHA+SGVyZSBhcmUgdGhlIGRpZmZlcmVudCB3YXlzIEZKIGNvdWxkIGhhdmUgcHJvZHVjZWQgQUJBQkE6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+U3RhcnQgd2l0aCBBQkEgLSZndDsgQUIrQUJBPFwvbGk+XHJcblx0PGxpPlN0YXJ0IHdpdGggQUJBIC0mZ3Q7IEFCQStCQTxcL2xpPlxyXG5cdDxsaT5TdGFydCB3aXRoIEFCIC0mZ3Q7IEFCK0EgLSZndDsgQUIrQUJBPFwvbGk+XHJcblx0PGxpPlN0YXJ0IHdpdGggQUIgLSZndDsgQUIrQSAtJmd0OyBBQkErQkE8XC9saT5cclxuXHQ8bGk+U3RhcnQgd2l0aCBCQSAtJmd0OyBBK0JBIC0mZ3Q7IEFCK0FCQTxcL2xpPlxyXG5cdDxsaT5TdGFydCB3aXRoIEJBIC0mZ3Q7IEErQkEgLSZndDsgQUJBK0JBPFwvbGk+XHJcblx0PGxpPlN0YXJ0IHdpdGggQUJBQiAtJmd0OyBBQkFCK0E8XC9saT5cclxuXHQ8bGk+U3RhcnQgd2l0aCBCQUJBIC0mZ3Q7IEErQkFCQTxcL2xpPlxyXG48XC9vbD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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