시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB152756851.515%

문제

상근이는 창영이가 보낸 비밀 메시지를 받았다. 메시지는 알파벳 대문자로만 이루어져 있으며, 길이는 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+QUJDQkMgKEFCQyArIEJDKTxcL2xpPlxyXG5cdDxsaT5BQkNDIChBQkMgKyBDKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWQ1NzRcdWIzYzVcdWM3NDQgXHVjNjQ0XHViOGNjXHVkNTVjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM1ZjBcdWMwYjBcdWM3NDAgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWMyMThcdWQ1ODlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHViNGUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWFjMTlcdWIzNTRcdWI3N2NcdWIzYzQsIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWJjMjlcdWJjOTVcdWM3NzQgXHViMmU0XHViOTc0XHViMmU0XHViYTc0IFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjZTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBBQVx1YzVkMFx1YzExYyBBQUFcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWNkMWQgNFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDU3NFx1YjNjNSBcdWM2NDRcdWI4Y2NcdWQ1NWMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZTM4XHVjNzc0XHViMjk0IDEwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNjOThcdWM3NGMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAyXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHVhYzAwIFx1YjllNFx1YzZiMCBcdWNlZTRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIDIwMTRcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHViZDg4XHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+QUJBQkFcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWNkMWQgOFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+QUJBXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MSAtJmd0OyBBQiArIEFCQTxcL2xpPlxyXG5cdDxsaT5BQkFcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxIC0mZ3Q7IEFCQSArIEJBPFwvbGk+XHJcblx0PGxpPkFCXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MSAtJmd0OyBBQiArIEEgLSZndDsgQUIgKyBBQkE8XC9saT5cclxuXHQ8bGk+QUJcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxIC0mZ3Q7IEFCICsgQSAtJmd0OyBBQkEgKyBCQTxcL2xpPlxyXG5cdDxsaT5CQVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTEgLSZndDsgQSArIEJBIC0mZ3Q7IEFCICsgQUJBPFwvbGk+XHJcblx0PGxpPkJBXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MSAtJmd0OyBBICsgQkEgLSZndDsgQUJBICsgQkE8XC9saT5cclxuXHQ8bGk+QUJBQlx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTEgLSZndDsgQUJBQiArIEE8XC9saT5cclxuXHQ8bGk+QkFCQVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTEgLSZndDsgQSArIEJBQkE8XC9saT5cclxuPFwvb2w+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTk5MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNlY3JldCBDb2RlIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBoYXMgc2VjcmV0IG1lc3NhZ2UgdGhhdCBoZSB3YW50cyB0byBoaWRlIGZyb20gaGlzIGNvd3M7IHRoZSBtZXNzYWdlIGlzIGEgc3RyaW5nIG9mIGxlbmd0aCBhdCBsZWFzdCAyIGNvbnRhaW5pbmcgb25seSB0aGUgY2hhcmFjdGVycyBBLi5aLjxcL3A+XHJcblxyXG48cD5UbyBlbmNyeXB0IGhpcyBtZXNzYWdlLCBGSiBhcHBsaWVzIGEgc2VxdWVuY2Ugb2YgJnF1b3Q7b3BlcmF0aW9ucyZxdW90OyB0byBpdCwgd2hlcmUgYW4gb3BlcmF0aW9uIGFwcGxpZWQgdG8gYSBzdHJpbmcgUyBmaXJzdCBzaG9ydGVucyBTIGJ5IHJlbW92aW5nIGVpdGhlciBzb21lIChidXQgbm90IGFsbCkgb2YgdGhlIGluaXRpYWwgY2hhcmFjdGVycyBvciBzb21lIChidXQgbm90IGFsbCkgb2YgdGhlIGZpbmFsIGNoYXJhY3RlcnMgZnJvbSBTLCBhZnRlciB3aGljaCB0aGUgb3JpZ2luYWwgc3RyaW5nIFMgaXMgYXR0YWNoZWQgZWl0aGVyIGF0IHRoZSBiZWdpbm5pbmcgb3IgZW5kLiAmbmJzcDtGb3IgZXhhbXBsZSwgYSBzaW5nbGUgb3BlcmF0aW9uIHRvIHRoZSBzdHJpbmcgQUJDIGNvdWxkIHJlc3VsdCBpbiBlaWdodCBwb3NzaWJsZSBzdHJpbmdzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkFBQkM8XC9saT5cclxuXHQ8bGk+QUJBQkM8XC9saT5cclxuXHQ8bGk+QkNBQkM8XC9saT5cclxuXHQ8bGk+Q0FCQzxcL2xpPlxyXG5cdDxsaT5BQkNBPFwvbGk+XHJcblx0PGxpPkFCQ0FCPFwvbGk+XHJcblx0PGxpPkFCQ0JDPFwvbGk+XHJcblx0PGxpPkFCQ0M8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5HaXZlbiB0aGUgZmluYWwgZW5jcnlwdGVkIHN0cmluZywgcGxlYXNlIGNvdW50IHRoZSBudW1iZXIgb2YgcG9zc2libGUgd2F5cyBGSiBjb3VsZCBoYXZlIHByb2R1Y2VkIHRoaXMgc3RyaW5nIHVzaW5nIG9uZSBvciBtb3JlIHJlcGVhdGVkIG9wZXJhdGlvbnMgYXBwbGllZCB0byBzb21lIHNvdXJjZSBzdHJpbmcuICZuYnNwO09wZXJhdGlvbnMgYXJlIHRyZWF0ZWQgYXMgYmVpbmcgZGlzdGluY3QgZXZlbiBpZiB0aGV5IGdpdmUgdGhlIHNhbWUgZW5jcnlwdGlvbiBvZiBGSiYjMzk7cyBtZXNzYWdlLiAmbmJzcDtGb3IgZXhhbXBsZSwgdGhlcmUgYXJlIGZvdXIgZGlzdGluY3Qgc2VwYXJhdGUgd2F5cyB0byBvYnRhaW4gQUFBIGZyb20gQUEuPFwvcD5cclxuXHJcbjxwPlByaW50IHlvdXIgYW5zd2VyIG91dCBtb2R1bG8gMjAxNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBBIHNpbmdsZSBlbmNyeXB0ZWQgc3RyaW5nIG9mIGxlbmd0aCBhdCBtb3N0IDEwMC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IFRoZSBudW1iZXIgb2Ygd2F5cyBGSiBjb3VsZCBoYXZlIHByb2R1Y2VkIHRoaXMgc3RyaW5nIHdpdGggb25lIG9yIG1vcmUgc3VjY2Vzc2l2ZSBvcGVyYXRpb25zIGFwcGxpZWQgdG8gc29tZSBpbml0aWFsIHN0cmluZyBvZiBsZW5ndGggYXQgbGVhc3QgMiwgd3JpdHRlbiBvdXQgbW9kdWxvIDIwMTQuICZuYnNwO0lmIHRoZXJlIGFyZSBubyBzdWNoIHdheXMsIG91dHB1dCB6ZXJvLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5IZXJlIGFyZSB0aGUgZGlmZmVyZW50IHdheXMgRkogY291bGQgaGF2ZSBwcm9kdWNlZCBBQkFCQTo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5TdGFydCB3aXRoIEFCQSAtJmd0OyBBQitBQkE8XC9saT5cclxuXHQ8bGk+U3RhcnQgd2l0aCBBQkEgLSZndDsgQUJBK0JBPFwvbGk+XHJcblx0PGxpPlN0YXJ0IHdpdGggQUIgLSZndDsgQUIrQSAtJmd0OyBBQitBQkE8XC9saT5cclxuXHQ8bGk+U3RhcnQgd2l0aCBBQiAtJmd0OyBBQitBIC0mZ3Q7IEFCQStCQTxcL2xpPlxyXG5cdDxsaT5TdGFydCB3aXRoIEJBIC0mZ3Q7IEErQkEgLSZndDsgQUIrQUJBPFwvbGk+XHJcblx0PGxpPlN0YXJ0IHdpdGggQkEgLSZndDsgQStCQSAtJmd0OyBBQkErQkE8XC9saT5cclxuXHQ8bGk+U3RhcnQgd2l0aCBBQkFCIC0mZ3Q7IEFCQUIrQTxcL2xpPlxyXG5cdDxsaT5TdGFydCB3aXRoIEJBQkEgLSZndDsgQStCQUJBPFwvbGk+XHJcbjxcL29sPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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