시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 3 3 75.000%

문제

이진 트리를 인오더(in-order)와 포스트오더(post-order)로 순회한 결과가 주어졌을 때, 프리오더(pre-order)로 순회한 결과를 찾을 수 있다. 또, 인오더와 포리오더로 순회한 결과가 주어졌을 때, 포스트오더로 순회한 결과도 쉽게 찾을 수 있다. 하지만, 프리오더와 포스트오더로 순회한 결과가 주어졌을 때는, 인오더로 순회한 결과를 구할 수 없다.

아래 이진 트리 4개를 보자.

위의 트리는 같은 프리오더와 포스트오더를 갖는 트리이다. 이러한 현상은 이진 트리에서만 나타나는 것이 아니고, 모든 m진 트리(자식이 최대 m개인 트리)에서 나타난다.

m진 트리를 프리오더와 포스트오더로 순회한 결과가 주어졌을 때, 이러한 순회 결과를 갖는 트리의 개수를 출력하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 다음과 같은 형식이다.

m s1 s2

이 뜻은 m진트리를 프리오더 순회한 결과가 s1, 포스트오더로 순회한 결과가 s2라는 뜻이다. (1 ≤ m ≤ 20, 1 ≤ s1,s2의 길이 ≤ 26, s1의 길이 = s2의 길이) s1의 길이가 k일 때, 알파벳 첫 k개 문자가 사용된다. 마지막 줄은 0이 주어진다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 프리오더와 포스트오더 순회 결과를 갖는 m진트리의 개수를 출력한다. 이 결과는 항상 부호있는 32비트 정수 범위이다. 입력으로 주어진 결과를 이용해서 트리를 적어도 하나는 만들 수 있다.

예제 입력 1

2 abc cba
2 abc bca
10 abc bca
13 abejkcfghid jkebfghicda
0

예제 출력 1

4
1
45
207352860
W3sicHJvYmxlbV9pZCI6IjQyNTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1MDRcdWI5YWNcdWM2MjRcdWIzNTQgXHVkM2VjXHVjMmE0XHVkMmI4XHVjNjI0XHViMzU0IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM3NzRcdWM5YzQgXHVkMmI4XHViOWFjXHViOTdjIFx1Yzc3OFx1YzYyNFx1YjM1NChpbi1vcmRlcilcdWM2NDAgXHVkM2VjXHVjMmE0XHVkMmI4XHVjNjI0XHViMzU0KHBvc3Qtb3JkZXIpXHViODVjIFx1YzIxY1x1ZDY4Y1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNTA0XHViOWFjXHVjNjI0XHViMzU0KHByZS1vcmRlcilcdWI4NWMgXHVjMjFjXHVkNjhjXHVkNTVjIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWM3NzhcdWM2MjRcdWIzNTRcdWM2NDAgXHVkM2VjXHViOWFjXHVjNjI0XHViMzU0XHViODVjIFx1YzIxY1x1ZDY4Y1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkM2VjXHVjMmE0XHVkMmI4XHVjNjI0XHViMzU0XHViODVjIFx1YzIxY1x1ZDY4Y1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWIzYzQgXHVjMjdkXHVhYzhjIFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1ZDUwNFx1YjlhY1x1YzYyNFx1YjM1NFx1YzY0MCBcdWQzZWNcdWMyYTRcdWQyYjhcdWM2MjRcdWIzNTRcdWI4NWMgXHVjMjFjXHVkNjhjXHVkNTVjIFx1YWNiMFx1YWNmY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjXHViMjk0LCBcdWM3NzhcdWM2MjRcdWIzNTRcdWI4NWMgXHVjMjFjXHVkNjhjXHVkNTVjIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWFkNmNcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNTQ0XHViNzk4IFx1Yzc3NFx1YzljNCBcdWQyYjhcdWI5YWMgNFx1YWMxY1x1Yjk3YyBcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcHJlcG9zdC5wbmdcIiBzdHlsZT1cIndpZHRoOiAyMzBweDsgaGVpZ2h0OiAxMTZweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzA0XHVjNzU4IFx1ZDJiOFx1YjlhY1x1YjI5NCBcdWFjMTlcdWM3NDAgXHVkNTA0XHViOWFjXHVjNjI0XHViMzU0XHVjNjQwIFx1ZDNlY1x1YzJhNFx1ZDJiOFx1YzYyNFx1YjM1NFx1Yjk3YyBcdWFjMTZcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzc0XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVkNjA0XHVjMGMxXHVjNzQwIFx1Yzc3NFx1YzljNCBcdWQyYjhcdWI5YWNcdWM1ZDBcdWMxMWNcdWI5Y2MgXHViMDk4XHVkMGMwXHViMDk4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM1NDRcdWIyYzhcdWFjZTAsIFx1YmFhOFx1YjRlMCBtXHVjOWM0IFx1ZDJiOFx1YjlhYyhcdWM3OTBcdWMyZGRcdWM3NzQgXHVjZDVjXHViMzAwIG1cdWFjMWNcdWM3NzggXHVkMmI4XHViOWFjKVx1YzVkMFx1YzExYyBcdWIwOThcdWQwYzBcdWIwOWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdG1cdWM5YzQgXHVkMmI4XHViOWFjXHViOTdjIFx1ZDUwNFx1YjlhY1x1YzYyNFx1YjM1NFx1YzY0MCBcdWQzZWNcdWMyYTRcdWQyYjhcdWM2MjRcdWIzNTRcdWI4NWMgXHVjMjFjXHVkNjhjXHVkNTVjIFx1YWNiMFx1YWNmY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMjFjXHVkNjhjIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWFjMTZcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWMyZGRcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0bSBzMSBzMjxcL3A+XHJcbjxwPlxyXG5cdFx1Yzc3NCBcdWI3M2JcdWM3NDAgbVx1YzljNFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWQ1MDRcdWI5YWNcdWM2MjRcdWIzNTQgXHVjMjFjXHVkNjhjXHVkNTVjIFx1YWNiMFx1YWNmY1x1YWMwMCBzMSwgXHVkM2VjXHVjMmE0XHVkMmI4XHVjNjI0XHViMzU0XHViODVjIFx1YzIxY1x1ZDY4Y1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWFjMDAgczJcdWI3N2NcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiAoMSAmbGU7IG0gJmxlOyAyMCwgMSAmbGU7IHMxLHMyXHVjNzU4IFx1YWUzOFx1Yzc3NCAmbGU7IDI2LCBzMVx1Yzc1OCBcdWFlMzhcdWM3NzQgPSBzMlx1Yzc1OCBcdWFlMzhcdWM3NzQpIHMxXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBrXHVjNzdjIFx1YjU0YywgXHVjNTRjXHVkMzBjXHViY2IzIFx1Y2NhYiBrXHVhYzFjIFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWMwYWNcdWM2YTlcdWI0MWNcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM3NDAgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDUwNFx1YjlhY1x1YzYyNFx1YjM1NFx1YzY0MCBcdWQzZWNcdWMyYTRcdWQyYjhcdWM2MjRcdWIzNTQgXHVjMjFjXHVkNjhjIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWFjMTZcdWIyOTQgbVx1YzljNFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhY2IwXHVhY2ZjXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWJkODBcdWQ2MzhcdWM3ODhcdWIyOTQgMzJcdWJlNDRcdWQyYjggXHVjODE1XHVjMjE4IFx1YmM5NFx1YzcwNFx1Yzc3NFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4XHViMjk0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQyNTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcmUtUG9zdC1lcm91cyEiLCJkZXNjcmlwdGlvbiI6IjxwPldlIGFyZSBhbGwgZmFtaWxpYXIgd2l0aCBwcmUtb3JkZXIsIGluLW9yZGVyIGFuZCBwb3N0LW9yZGVyIHRyYXZlcnNhbHMgb2YgYmluYXJ5IHRyZWVzLiBBIGNvbW1vbiBwcm9ibGVtIGluIGRhdGEgc3RydWN0dXJlIGNsYXNzZXMgaXMgdG8gXHVmYjAxbmQgdGhlIHByZS1vcmRlciB0cmF2ZXJzYWwgb2YgYSBiaW5hcnkgdHJlZSB3aGVuIGdpdmVuIHRoZSBpbi1vcmRlciBhbmQgcG9zdC1vcmRlciB0cmF2ZXJzYWxzLiBBbHRlcm5hdGl2ZWx5LCB5b3UgY2FuIFx1ZmIwMW5kIHRoZSBwb3N0LW9yZGVyIHRyYXZlcnNhbCB3aGVuIGdpdmVuIHRoZSBpbi1vcmRlciBhbmQgcHJlLW9yZGVyLiBIb3dldmVyLCBpbiBnZW5lcmFsIHlvdSBjYW5ub3QgZGV0ZXJtaW5lIHRoZSBpbi1vcmRlciB0cmF2ZXJzYWwgb2YgYSB0cmVlIHdoZW4gZ2l2ZW4gaXRzIHByZS1vcmRlciBhbmQgcG9zdC1vcmRlciB0cmF2ZXJzYWxzLiBDb25zaWRlciB0aGUgZm91ciBiaW5hcnkgdHJlZXMgYmVsb3c6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcHJlcG9zdC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTZweDsgd2lkdGg6MjMwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QWxsIG9mIHRoZXNlIHRyZWVzIGhhdmUgdGhlIHNhbWUgcHJlLW9yZGVyIGFuZCBwb3N0LW9yZGVyIHRyYXZlcnNhbHMuIFRoaXMgcGhlbm9tZW5vbiBpcyBub3QgcmVzdHJpY3RlZCB0byBiaW5hcnkgdHJlZXMsIGJ1dCBob2xkcyBmb3IgZ2VuZXJhbCBtLWFyeSB0cmVlcyBhcyB3ZWxsLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgd2lsbCBjb25zaXN0IG9mIG11bHRpcGxlIHByb2JsZW0gaW5zdGFuY2VzLiBFYWNoIGluc3RhbmNlIHdpbGwgY29uc2lzdCBvZiBhIGxpbmUgb2YgdGhlIGZvcm08XC9wPlxyXG5cclxuPHA+bSBzMSBzMjxcL3A+XHJcblxyXG48cD5pbmRpY2F0aW5nIHRoYXQgdGhlIHRyZWVzIGFyZSBtLWFyeSB0cmVlcywgczEgaXMgdGhlIHByZS1vcmRlciB0cmF2ZXJzYWwgYW5kIHMyIGlzIHRoZSBwb3N0LW9yZGVyIHRyYXZlcnNhbC4gQWxsIHRyYXZlcnNhbCBzdHJpbmdzIHdpbGwgY29uc2lzdCBvZiBsb3dlcmNhc2UgYWxwaGFiZXRpYyBjaGFyYWN0ZXJzLiBGb3IgYWxsIGlucHV0IGluc3RhbmNlcywgMSAmbGU7IG0gJmxlOyAyMCBhbmQgdGhlIGxlbmd0aCBvZiBzMSBhbmQgczIgd2lsbCBiZSBiZXR3ZWVuIDEgYW5kIDI2IGluY2x1c2l2ZS4gSWYgdGhlIGxlbmd0aCBvZiBzMSBpcyBrICh3aGljaCBpcyB0aGUgc2FtZSBhcyB0aGUgbGVuZ3RoIG9mIHMyLCBvZiBjb3Vyc2UpLCB0aGUgXHVmYjAxcnN0IGsgbGV0dGVycyBvZiB0aGUgYWxwaGFiZXQgd2lsbCBiZSB1c2VkIGluIHRoZSBzdHJpbmdzLiBBbiBpbnB1dCBsaW5lIG9mIDAgd2lsbCB0ZXJtaW5hdGUgdGhlIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHByb2JsZW0gaW5zdGFuY2UsIHlvdSBzaG91bGQgb3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciBvZiBwb3NzaWJsZSB0cmVlcyB3aGljaCB3b3VsZCByZXN1bHQgaW4gdGhlIHByZS1vcmRlciBhbmQgcG9zdC1vcmRlciB0cmF2ZXJzYWxzIGZvciB0aGUgaW5zdGFuY2UuIEFsbCBvdXRwdXQgdmFsdWVzIHdpbGwgYmUgd2l0aGluIHRoZSByYW5nZSBvZiBhIDMyLWJpdCBzaWduZWQgaW50ZWdlci4gRm9yIGVhY2ggcHJvYmxlbSBpbnN0YW5jZSwgeW91IGFyZSBndWFyYW50ZWVkIHRoYXQgdGhlcmUgaXMgYXQgbGVhc3Qgb25lIHRyZWUgd2l0aCB0aGUgZ2l2ZW4gcHJlLW9yZGVyIGFuZCBwb3N0LW9yZGVyIHRyYXZlcnNhbHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d