시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB131514438.938%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

ABABABA

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjIwODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJhODcgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVkMmI4XHViOWFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1ZDJiOFx1YjlhY1x1YjI5NCBcdWI4ZThcdWQyYjhcdWFjMDAgXHVjNzg4XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YmE3MCwgXHVhYzAxIFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1Yzc5MFx1YzJkZCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVhYzAwXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM1ZDBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM4MDFcdWQ2MDAgXHVjNzg4XHViMmU0LiBcdWFjMTlcdWM3NDAgXHViYjM4XHVjNzkwXHVhYzAwIFx1YzVlY1x1YjdlYyBcdWM4MTVcdWM4MTBcdWM1ZDAgXHVjODAxXHVkNjAwIFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVkMmI4XHViOWFjXHViOTdjIFx1YjhlOFx1ZDJiOFx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NzRcdWMxMWMgXHVkMGQwXHVjMGM5XHVkNTU4XHViMjk0XHViMzcwLCBcdWM1YjRcdWI1YTQgXHVkNTVjIFx1YzgxNVx1YzgxMFx1YzVkMFx1YzExY1x1YjI5NCBcdWFkZjggXHVjODE1XHVjODEwXHVjNzU4IFx1Yzc5MFx1YzJkZFx1YjRlNCBcdWM5MTEgXHVjNjdjXHVjYWJkIFx1Yzc5MFx1YzJkZFx1YjRlNFx1YmQ4MFx1ZDEzMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHViYzI5XHViYjM4XHVkNTc0IFx1YjA5OFx1YWMwNFx1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWQwZDBcdWMwYzlcdWQ1NThcdWJhNzQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjOGZjXHVjNzU4XHVkNTYwIFx1YzgxMFx1Yzc0MCwgXHVjNzkwXHVjMmRkXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzVlY1x1YjdlYyBcdWJjODggXHViYzI5XHViYjM4XHViNDIwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyOTRcdWIzNzAoXHVjODFjXHVjNzdjIFx1Y2M5OFx1Yzc0YyBcdWJjMjlcdWJiMzhcdWQ1NjAgXHViNTRjXHVjNjQwLCBcdWM3OTBcdWMyZGQgXHVjODE1XHVjODEwXHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YWNlMCBcdWIyZTRcdWMyZGMgXHViM2NjXHVjNTQ0XHVjNjJjIFx1YjU0YyksIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVkNTVjIFx1YzgxNVx1YzgxMFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YWNiZFx1Yjg1Y1x1YzVkMCBcdWIwOThcdWQwYzBcdWIwYTAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgaGVpZ2h0PVwiMTc1XCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDdcL3RydHJ0cnRyLnBuZ1wiIHdpZHRoPVwiNTY3XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVhY2JkXHViODVjXHVhYzAwIEFCQUJBQkFcdWM3NzggXHVhY2JkXHVjNmIwXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM1NDRcdWI3OThcdWNhYmRcdWM3NzQgXHViOGU4XHVkMmI4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YmE3MCwgXHVjNzA0XHViODVjIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWFjODNcdWM3NzQgXHVjNzkwXHVjMmRkIFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjNjdjXHVjYWJkIFx1Yzc5MFx1YzJkZFx1Yzc0NCBcdWM2N2NcdWNhYmRcdWM1ZDAgXHViMDk4XHVkMGMwXHViMGM4XHViMjk0XHViMzcwLCBcdWIzMDBcdWJkODBcdWJkODRcdWM3NTggXHVjMGFjXHViNzhjXHVjNzc0IFx1YzBkZFx1YWMwMVx1ZDU1OFx1YjI5NCBcdWFkZjhcdWI5YmNcdWNjOThcdWI3ZmMgXHViOGU4XHVkMmI4XHVhYzAwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZGY4XHViOWJjXHVjNzNjXHViODVjIFx1YWNlMFx1Y2U1OFx1YjgyNFx1YmE3NCwgXHVjODhjXHVjNmIwIFx1YjMwMFx1Y2U2ZFx1Yzc0NCBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWJiM2NcdWI4NjAgXHViMmY1XHVjNWQwXHViMjk0IFx1YmNjMFx1ZDY1NFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVhY2JkXHViODVjXHViOTdjIFx1YWMxNlx1YjI5NCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWRmOCBcdWFlMzhcdWM3NzRcdWFjMDAgMzAwXHVjNzkwXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIDEsMDAwLDAwMCwwMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjA4OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkV4cGxvcmluZyBQeXJhbWlkcyIsImRlc2NyaXB0aW9uIjoiPHA+QXJjaGFlb2xvZ2lzdHMgaGF2ZSBkaXNjb3ZlcmVkIGEgbmV3IHNldCBvZiBoaWRkZW4gY2F2ZXMgaW4gb25lIG9mIHRoZSBFZ3lwdGlhbiBweXJhbWlkcy4gVGhlIGRlY3J5cHRpb24gb2YgYW5jaWVudCBoaWVyb2dseXBocyBvbiB0aGUgd2FsbHMgbmVhcmJ5IHNob3dlZCB0aGF0IHRoZSBjYXZlcyBzdHJ1Y3R1cmUgaXMgYXMgZm9sbG93cy4gVGhlcmUgYXJlIG4gY2F2ZXMgaW4gYSBweXJhbWlkLCBjb25uZWN0ZWQgYnkgbmFycm93IHBhc3NhZ2VzLCBvbmUgb2YgdGhlIGNhdmVzIGlzIGNvbm5lY3RlZCBieSBhIHBhc3NhZ2UgdG8gdGhlIG91dGVyIHdvcmxkLiBUaGUgc3lzdGVtIG9mIHRoZSBwYXNzYWdlcyBpcyBvcmdhbml6ZWQgaW4gc3VjaCBhIHdheSwgdGhhdCB0aGVyZSBpcyBleGFjdGx5IG9uZSB3YXkgdG8gZ2V0IGZyb20gb3V0c2lkZSB0byBlYWNoIGNhdmUgYWxvbmcgcGFzc2FnZXMuIEFsbCBjYXZlcyBhcmUgbG9jYXRlZCBpbiB0aGUgYmFzZW1lbnQgb2YgdGhlIHB5cmFtaWQsIHNvIHdlIGNhbiBjb25zaWRlciB0aGVtIGJlaW5nIGxvY2F0ZWQgaW4gdGhlIHNhbWUgcGxhbmUuIFBhc3NhZ2VzIGRvIG5vdCBpbnRlcnNlY3QuIEVhY2ggY2F2ZSBoYXMgaXRzIHdhbGxzIGNvbG9yZWQgaW4gb25lIG9mIHNldmVyYWwgdmFyaW91cyBjb2xvcnMuPFwvcD5cclxuXHJcbjxwPlRoZSBzY2llbnRpc3RzIGhhdmUgZGVjaWRlZCB0byBjcmVhdGUgYSBtb3JlIGRldGFpbGVkIGRlc2NyaXB0aW9uIG9mIHRoZSBjYXZlcywgc28gdGhleSBkZWNpZGVkIHRvIHVzZSBhbiBleHBsb3Jpbmcgcm9ib3QuIFRoZSByb2JvdCB0aGV5IGFyZSBwbGFubmluZyB0byB1c2UgaGFzIHR3byB0eXBlcyBvZiBtZW1vcnkgJm1kYXNoOyB0aGUgb3V0cHV0IHRhcGUsIHdoaWNoIGlzIHVzZWQgZm9yIHdyaXRpbmcgZG93biB0aGUgZGVzY3JpcHRpb24gb2YgdGhlIGNhdmVzLCBhbmQgdGhlIG9wZXJhdGluZyBtZW1vcnkgb3JnYW5pemVkIGFzIGEgc3RhY2suPFwvcD5cclxuXHJcbjxwPlRoZSByb2JvdCBmaXJzdCBlbnRlcnMgdGhlIGNhdmUgY29ubmVjdGVkIHRvIHRoZSBvdXRlciB3b3JsZCBhbG9uZyB0aGUgcGFzc2FnZS4gV2hlbiBpdCB0cmF2ZWxzIGFsb25nIGFueSBwYXNzYWdlIGZvciB0aGUgZmlyc3QgdGltZSwgaXQgcHV0cyBpdHMgZGVzY3JpcHRpb24gb24gdGhlIHRvcCBvZiBpdHMgc3RhY2suIFdoZW4gdGhlIHJvYm90IGVudGVycyBhbnkgY2F2ZSwgaXQgcHJpbnRzIHRoZSBjb2xvciBvZiBpdHMgd2FsbHMgdG8gaXRzIG91dHB1dCB0YXBlLiBBZnRlciB0aGF0IGl0IGNob29zZXMgdGhlIGxlZnRtb3N0IHBhc3NhZ2UgYW1vbmcgdGhvc2UgdGhhdCBpdCBoYXMgbm90IHlldCB0cmF2ZWxsZWQgYW5kIGdvZXMgYWxvbmcgaXQuIElmIHRoZXJlIGlzIG5vIHN1Y2ggcGFzc2FnZSwgdGhlIHJvYm90IHRha2VzIHRoZSBwYXNzYWdlIGRlc2NyaXB0aW9uIGZyb20gdGhlIHRvcCBvZiBpdHMgc3RhY2sgYW5kIHRyYXZlbHMgYWxvbmcgaXQgaW4gdGhlIHJldmVyc2UgZGlyZWN0aW9uLiBUaGUgcm9ib3QmcnNxdW87cyB0YXNrIGlzIG92ZXIgd2hlbiBpdCByZXR1cm5zIHRvIHRoZSBvdXRzaWRlIG9mIHRoZSBweXJhbWlkLiBJdCBpcyBlYXN5IHRvIHNlZSB0aGF0IGR1cmluZyBpdHMgdHJpcCB0aGUgcm9ib3QgdmlzaXRzIGVhY2ggY2F2ZSBhdCBsZWFzdCBvbmNlIGFuZCB0cmF2ZWxzIGFsb25nIGVhY2ggcGFzc2FnZSBleGFjdGx5IG9uY2UgaW4gZWFjaCBkaXJlY3Rpb24uPFwvcD5cclxuXHJcbjxwPlRoZSBzY2llbnRpc3RzIGhhdmUgc2VudCB0aGUgcm9ib3QgdG8gaXRzIG1pc3Npb24uIEFmdGVyIGl0IHJldHVybmVkIHRoZXkgc3RhcnRlZCB0byBzdHVkeSB0aGUgb3V0cHV0IHRhcGUuIFdoYXQgYSBncmVhdCBkaXNhcHBvaW50bWVudCB0aGV5IGhhdmUgaGFkIGFmdGVyIHRoZXkgaGF2ZSB1bmRlcnN0b29kIHRoYXQgdGhlIG91dHB1dCB0YXBlIGRvZXMgbm90IGRlc2NyaWJlIHRoZSBjYXZlIHN5c3RlbSB1bmlxdWVseS4gTm93IHRoZXkgaGF2ZSBhIG5ldyBwcm9ibGVtICZtZGFzaDsgdGhleSB3YW50IHRvIGtub3cgaG93IG1hbnkgZGlcdWZiMDBlcmVudCBjYXZlIHN5c3RlbXMgY291bGQgaGF2ZSBwcm9kdWNlZCB0aGUgb3V0cHV0IHRhcGUgdGhleSBoYXZlLiBIZWxwIHRoZW0gdG8gZmluZCB0aGF0IG91dC48XC9wPlxyXG5cclxuPHA+U2luY2UgdGhlIHJlcXVlc3RlZCBudW1iZXIgY2FuIGJlIHF1aXRlIGxhcmdlLCB5b3Ugc2hvdWxkIG91dHB1dCBpdCBtb2R1bG8gMSAwMDAgMDAwIDAwMC4gUGxlYXNlIG5vdGUsIHRoYXQgdGhlIGFic29sdXRlIGxvY2F0aW9ucyBvZiB0aGUgY2F2ZXMgYXJlIG5vdCBpbXBvcnRhbnQsIGJ1dCB0aGVpciByZWxhdGl2ZSBsb2NhdGlvbnMgYXJlIGltcG9ydGFudCwgc28gdGhlIGNhdmVzIChjKSBhbmQgKGQpIG9uIHRoZSBwaWN0dXJlIGJlbG93IGFyZSBjb25zaWRlcmVkIGRpXHVmYjAwZXJlbnQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcHlyYW1pZC5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTVweDsgd2lkdGg6NjU0cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIGNvbnRhaW5zIHRoZSBvdXRwdXQgdGFwZSB0aGF0IHRoZSBhcmNoYWVvbG9naXN0cyBoYXZlLiBUaGUgb3V0cHV0IHRhcGUgaXMgdGhlIHNlcXVlbmNlIG9mIGNvbG9ycyBvZiBjYXZlcyBpbiBvcmRlciB0aGUgcm9ib3QgdmlzaXRlZCB0aGVtLiBUaGUgY29sb3JzIGFyZSBkZW5vdGVkIGJ5IGNhcGl0YWwgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldC4gVGhlIGxlbmd0aCBvZiB0aGUgdGFwZSBkb2VzIG5vdCBleGNlZWQgMzAwIGNoYXJhY3RlcnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG9uZSBpbnRlZ2VyIG51bWJlciAmbWRhc2g7IHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IGNhdmUgc3lzdGVtcyAobW9kdWxvIDEgMDAwIDAwMCAwMDApIHRoYXQgY291bGQgcHJvZHVjZSB0aGUgb3V0cHV0IHRhcGUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==