시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 50 26 22 47.826%

문제

몇 개의 정점으로 이루어진 트리가 있다. 이 트리는 루트가 있는 트리이며, 각 정점은 몇 개의 자식 정점을 가질 수 있다. 각각의 정점에는 알파벳 대문자가 적혀 있다. 같은 문자가 여러 정점에 적혀 있을 수도 있다.

이 트리를 루트부터 시작해서 탐색하는데, 어떤 한 정점에서는 그 정점의 자식들 중 왼쪽 자식들부터 차례대로 방문해 나간다. 이와 같이 탐색하면 하나의 경로를 얻을 수 있다. 주의할 점은, 자식이 있는 정점의 경우에는 여러 번 방문될 수도 있는데(제일 처음 방문할 때와, 자식 정점을 방문하고 다시 돌아올 때), 그러한 경우에 한 정점이 여러 번 경로에 나타날 수도 있다는 것이다.

위의 그림은 경로가 ABABABA인 경우를 모두 나타낸 것이다. 아래쪽이 루트를 의미하며, 위로 연결된 것이 자식 노드를 의미한다. 위의 그림에서는 왼쪽 자식을 왼쪽에 나타냈는데, 대부분의 사람이 생각하는 그림처럼 루트가 위에 있는 그림으로 고치려면, 좌우 대칭을 해야 한다. 물론 답에는 변화가 없다.

경로가 주어졌을 때, 그러한 경로를 갖는 트리의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 경로가 주어진다. 이는 알파벳 대문자로만 이루어지며, 그 길이가 300자를 넘지 않는다.

출력

첫째 줄에 트리의 개수를 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

ABABABA

예제 출력 1

5

힌트

W3sicHJvYmxlbV9pZCI6IjIwODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJhODcgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVkMmI4XHViOWFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1ZDJiOFx1YjlhY1x1YjI5NCBcdWI4ZThcdWQyYjhcdWFjMDAgXHVjNzg4XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YmE3MCwgXHVhYzAxIFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1Yzc5MFx1YzJkZCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVhYzAwXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM1ZDBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM4MDFcdWQ2MDAgXHVjNzg4XHViMmU0LiBcdWFjMTlcdWM3NDAgXHViYjM4XHVjNzkwXHVhYzAwIFx1YzVlY1x1YjdlYyBcdWM4MTVcdWM4MTBcdWM1ZDAgXHVjODAxXHVkNjAwIFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbjxwPlx1Yzc3NCBcdWQyYjhcdWI5YWNcdWI5N2MgXHViOGU4XHVkMmI4XHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzExYyBcdWQwZDBcdWMwYzlcdWQ1NThcdWIyOTRcdWIzNzAsIFx1YzViNFx1YjVhNCBcdWQ1NWMgXHVjODE1XHVjODEwXHVjNWQwXHVjMTFjXHViMjk0IFx1YWRmOCBcdWM4MTVcdWM4MTBcdWM3NTggXHVjNzkwXHVjMmRkXHViNGU0IFx1YzkxMSBcdWM2N2NcdWNhYmQgXHVjNzkwXHVjMmRkXHViNGU0XHViZDgwXHVkMTMwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWJjMjlcdWJiMzhcdWQ1NzQgXHViMDk4XHVhYzA0XHViMmU0LiBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1ZDBkMFx1YzBjOVx1ZDU1OFx1YmE3NCBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2JkXHViODVjXHViOTdjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM4ZmNcdWM3NThcdWQ1NjAgXHVjODEwXHVjNzQwLCBcdWM3OTBcdWMyZGRcdWM3NzQgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWJjMjlcdWJiMzhcdWI0MjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjI5NFx1YjM3MChcdWM4MWNcdWM3N2MgXHVjYzk4XHVjNzRjIFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWI1NGNcdWM2NDAsIFx1Yzc5MFx1YzJkZCBcdWM4MTVcdWM4MTBcdWM3NDQgXHViYzI5XHViYjM4XHVkNTU4XHVhY2UwIFx1YjJlNFx1YzJkYyBcdWIzY2NcdWM1NDRcdWM2MmMgXHViNTRjKSwgXHVhZGY4XHViN2VjXHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMCBcdWQ1NWMgXHVjODE1XHVjODEwXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWJjODggXHVhY2JkXHViODVjXHVjNWQwIFx1YjA5OFx1ZDBjMFx1YjBhMCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG48cD48aW1nIHdpZHRoPVwiNTY3XCIgaGVpZ2h0PVwiMTc1XCIgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDdcL3RydHJ0cnRyLnBuZ1wiIFwvPjxcL3A+XHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVhY2JkXHViODVjXHVhYzAwIEFCQUJBQkFcdWM3NzggXHVhY2JkXHVjNmIwXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM1NDRcdWI3OThcdWNhYmRcdWM3NzQgXHViOGU4XHVkMmI4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YmE3MCwgXHVjNzA0XHViODVjIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWFjODNcdWM3NzQgXHVjNzkwXHVjMmRkIFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjNjdjXHVjYWJkIFx1Yzc5MFx1YzJkZFx1Yzc0NCBcdWM2N2NcdWNhYmRcdWM1ZDAgXHViMDk4XHVkMGMwXHViMGM4XHViMjk0XHViMzcwLCBcdWIzMDBcdWJkODBcdWJkODRcdWM3NTggXHVjMGFjXHViNzhjXHVjNzc0IFx1YzBkZFx1YWMwMVx1ZDU1OFx1YjI5NCBcdWFkZjhcdWI5YmNcdWNjOThcdWI3ZmMgXHViOGU4XHVkMmI4XHVhYzAwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZGY4XHViOWJjXHVjNzNjXHViODVjIFx1YWNlMFx1Y2U1OFx1YjgyNFx1YmE3NCwgXHVjODhjXHVjNmIwIFx1YjMwMFx1Y2U2ZFx1Yzc0NCBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWJiM2NcdWI4NjAgXHViMmY1XHVjNWQwXHViMjk0IFx1YmNjMFx1ZDY1NFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuPHA+XHVhY2JkXHViODVjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFjYmRcdWI4NWNcdWI5N2MgXHVhYzE2XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTc0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2JkXHViODVjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWMwXHViYTcwLCBcdWFkZjggXHVhZTM4XHVjNzc0XHVhYzAwIDMwMFx1Yzc5MFx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIDEsMDAwLDAwMCwwMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMDg4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRXhwbG9yaW5nIFB5cmFtaWRzIiwiZGVzY3JpcHRpb24iOiI8cD5BcmNoYWVvbG9naXN0cyBoYXZlIGRpc2NvdmVyZWQgYSBuZXcgc2V0IG9mIGhpZGRlbiBjYXZlcyBpbiBvbmUgb2YgdGhlIEVneXB0aWFuIHB5cmFtaWRzLiBUaGUgZGVjcnlwdGlvbiBvZiBhbmNpZW50IGhpZXJvZ2x5cGhzIG9uIHRoZSB3YWxscyBuZWFyYnkgc2hvd2VkIHRoYXQgdGhlIGNhdmVzIHN0cnVjdHVyZSBpcyBhcyBmb2xsb3dzLiBUaGVyZSBhcmUgbiBjYXZlcyBpbiBhIHB5cmFtaWQsIGNvbm5lY3RlZCBieSBuYXJyb3cgcGFzc2FnZXMsIG9uZSBvZiB0aGUgY2F2ZXMgaXMgY29ubmVjdGVkIGJ5IGEgcGFzc2FnZSB0byB0aGUgb3V0ZXIgd29ybGQuIFRoZSBzeXN0ZW0gb2YgdGhlIHBhc3NhZ2VzIGlzIG9yZ2FuaXplZCBpbiBzdWNoIGEgd2F5LCB0aGF0IHRoZXJlIGlzIGV4YWN0bHkgb25lIHdheSB0byBnZXQgZnJvbSBvdXRzaWRlIHRvIGVhY2ggY2F2ZSBhbG9uZyBwYXNzYWdlcy4gQWxsIGNhdmVzIGFyZSBsb2NhdGVkIGluIHRoZSBiYXNlbWVudCBvZiB0aGUgcHlyYW1pZCwgc28gd2UgY2FuIGNvbnNpZGVyIHRoZW0gYmVpbmcgbG9jYXRlZCBpbiB0aGUgc2FtZSBwbGFuZS4gUGFzc2FnZXMgZG8gbm90IGludGVyc2VjdC4gRWFjaCBjYXZlIGhhcyBpdHMgd2FsbHMgY29sb3JlZCBpbiBvbmUgb2Ygc2V2ZXJhbCB2YXJpb3VzIGNvbG9ycy48XC9wPlxyXG5cclxuPHA+VGhlIHNjaWVudGlzdHMgaGF2ZSBkZWNpZGVkIHRvIGNyZWF0ZSBhIG1vcmUgZGV0YWlsZWQgZGVzY3JpcHRpb24gb2YgdGhlIGNhdmVzLCBzbyB0aGV5IGRlY2lkZWQgdG8gdXNlIGFuIGV4cGxvcmluZyByb2JvdC4gVGhlIHJvYm90IHRoZXkgYXJlIHBsYW5uaW5nIHRvIHVzZSBoYXMgdHdvIHR5cGVzIG9mIG1lbW9yeSAmbWRhc2g7IHRoZSBvdXRwdXQgdGFwZSwgd2hpY2ggaXMgdXNlZCBmb3Igd3JpdGluZyBkb3duIHRoZSBkZXNjcmlwdGlvbiBvZiB0aGUgY2F2ZXMsIGFuZCB0aGUgb3BlcmF0aW5nIG1lbW9yeSBvcmdhbml6ZWQgYXMgYSBzdGFjay48XC9wPlxyXG5cclxuPHA+VGhlIHJvYm90IGZpcnN0IGVudGVycyB0aGUgY2F2ZSBjb25uZWN0ZWQgdG8gdGhlIG91dGVyIHdvcmxkIGFsb25nIHRoZSBwYXNzYWdlLiBXaGVuIGl0IHRyYXZlbHMgYWxvbmcgYW55IHBhc3NhZ2UgZm9yIHRoZSBmaXJzdCB0aW1lLCBpdCBwdXRzIGl0cyBkZXNjcmlwdGlvbiBvbiB0aGUgdG9wIG9mIGl0cyBzdGFjay4gV2hlbiB0aGUgcm9ib3QgZW50ZXJzIGFueSBjYXZlLCBpdCBwcmludHMgdGhlIGNvbG9yIG9mIGl0cyB3YWxscyB0byBpdHMgb3V0cHV0IHRhcGUuIEFmdGVyIHRoYXQgaXQgY2hvb3NlcyB0aGUgbGVmdG1vc3QgcGFzc2FnZSBhbW9uZyB0aG9zZSB0aGF0IGl0IGhhcyBub3QgeWV0IHRyYXZlbGxlZCBhbmQgZ29lcyBhbG9uZyBpdC4gSWYgdGhlcmUgaXMgbm8gc3VjaCBwYXNzYWdlLCB0aGUgcm9ib3QgdGFrZXMgdGhlIHBhc3NhZ2UgZGVzY3JpcHRpb24gZnJvbSB0aGUgdG9wIG9mIGl0cyBzdGFjayBhbmQgdHJhdmVscyBhbG9uZyBpdCBpbiB0aGUgcmV2ZXJzZSBkaXJlY3Rpb24uIFRoZSByb2JvdCZyc3F1bztzIHRhc2sgaXMgb3ZlciB3aGVuIGl0IHJldHVybnMgdG8gdGhlIG91dHNpZGUgb2YgdGhlIHB5cmFtaWQuIEl0IGlzIGVhc3kgdG8gc2VlIHRoYXQgZHVyaW5nIGl0cyB0cmlwIHRoZSByb2JvdCB2aXNpdHMgZWFjaCBjYXZlIGF0IGxlYXN0IG9uY2UgYW5kIHRyYXZlbHMgYWxvbmcgZWFjaCBwYXNzYWdlIGV4YWN0bHkgb25jZSBpbiBlYWNoIGRpcmVjdGlvbi48XC9wPlxyXG5cclxuPHA+VGhlIHNjaWVudGlzdHMgaGF2ZSBzZW50IHRoZSByb2JvdCB0byBpdHMgbWlzc2lvbi4gQWZ0ZXIgaXQgcmV0dXJuZWQgdGhleSBzdGFydGVkIHRvIHN0dWR5IHRoZSBvdXRwdXQgdGFwZS4gV2hhdCBhIGdyZWF0IGRpc2FwcG9pbnRtZW50IHRoZXkgaGF2ZSBoYWQgYWZ0ZXIgdGhleSBoYXZlIHVuZGVyc3Rvb2QgdGhhdCB0aGUgb3V0cHV0IHRhcGUgZG9lcyBub3QgZGVzY3JpYmUgdGhlIGNhdmUgc3lzdGVtIHVuaXF1ZWx5LiBOb3cgdGhleSBoYXZlIGEgbmV3IHByb2JsZW0gJm1kYXNoOyB0aGV5IHdhbnQgdG8ga25vdyBob3cgbWFueSBkaVx1ZmIwMGVyZW50IGNhdmUgc3lzdGVtcyBjb3VsZCBoYXZlIHByb2R1Y2VkIHRoZSBvdXRwdXQgdGFwZSB0aGV5IGhhdmUuIEhlbHAgdGhlbSB0byBmaW5kIHRoYXQgb3V0LjxcL3A+XHJcblxyXG48cD5TaW5jZSB0aGUgcmVxdWVzdGVkIG51bWJlciBjYW4gYmUgcXVpdGUgbGFyZ2UsIHlvdSBzaG91bGQgb3V0cHV0IGl0IG1vZHVsbyAxIDAwMCAwMDAgMDAwLiBQbGVhc2Ugbm90ZSwgdGhhdCB0aGUgYWJzb2x1dGUgbG9jYXRpb25zIG9mIHRoZSBjYXZlcyBhcmUgbm90IGltcG9ydGFudCwgYnV0IHRoZWlyIHJlbGF0aXZlIGxvY2F0aW9ucyBhcmUgaW1wb3J0YW50LCBzbyB0aGUgY2F2ZXMgKGMpIGFuZCAoZCkgb24gdGhlIHBpY3R1cmUgYmVsb3cgYXJlIGNvbnNpZGVyZWQgZGlcdWZiMDBlcmVudC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9weXJhbWlkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1NXB4OyB3aWR0aDo2NTRweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGZpbGUgY29udGFpbnMgdGhlIG91dHB1dCB0YXBlIHRoYXQgdGhlIGFyY2hhZW9sb2dpc3RzIGhhdmUuIFRoZSBvdXRwdXQgdGFwZSBpcyB0aGUgc2VxdWVuY2Ugb2YgY29sb3JzIG9mIGNhdmVzIGluIG9yZGVyIHRoZSByb2JvdCB2aXNpdGVkIHRoZW0uIFRoZSBjb2xvcnMgYXJlIGRlbm90ZWQgYnkgY2FwaXRhbCBsZXR0ZXJzIG9mIHRoZSBFbmdsaXNoIGFscGhhYmV0LiBUaGUgbGVuZ3RoIG9mIHRoZSB0YXBlIGRvZXMgbm90IGV4Y2VlZCAzMDAgY2hhcmFjdGVycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGludGVnZXIgbnVtYmVyICZtZGFzaDsgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgY2F2ZSBzeXN0ZW1zIChtb2R1bG8gMSAwMDAgMDAwIDAwMCkgdGhhdCBjb3VsZCBwcm9kdWNlIHRoZSBvdXRwdXQgdGFwZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=