문제
n개의 정점으로 이루어진 루트가 있는 트리가 주어진다. 각 정점에는 1번부터 n번까지 번호가 매겨져 있다. 같은 번호를 가지는 정점은 없고, 힙을 형성하고 있다. 즉, 각 정점에 붙여있는 숫자는 부모의 정점에 붙어잇는 숫자보다 작다. 이렇게 번호를 붙이는 방법의 수를 구하는 프로그램을 작성하시오. 이 수는 매우 클 수 있기 때문에, m으로 나눈 나머지를 출력한다.
출력
각 테스트 케이스에 대해서, 입력으로 주어지는 조건을 만족하는 힙의 개수를 출력한다.
힌트
마지막 예제의 경우에 아래와 같이 8가지가 가능하다.
W3sicHJvYmxlbV9pZCI6Ijc4ODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3OTkgXHVjMTM4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5uXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViOGU4XHVkMmI4XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWQyYjhcdWI5YWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjODE1XHVjODEwXHVjNWQwXHViMjk0IDFcdWJjODhcdWJkODBcdWQxMzAgblx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWIyOTQgXHVjODE1XHVjODEwXHVjNzQwIFx1YzVjNlx1YWNlMCwgXHVkNzk5XHVjNzQ0IFx1ZDYxNVx1YzEzMVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzk4OSwgXHVhYzAxIFx1YzgxNVx1YzgxMFx1YzVkMCBcdWJkOTlcdWM1ZWNcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViMjk0IFx1YmQ4MFx1YmFhOFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM1ZDAgXHViZDk5XHVjNWI0XHVjNzg3XHViMjk0IFx1YzIyYlx1Yzc5MFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWJjODhcdWQ2MzhcdWI5N2MgXHViZDk5XHVjNzc0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1Yzc3NCBcdWMyMThcdWIyOTQgXHViOWU0XHVjNmIwIFx1ZDA3NCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgbVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IHQgKHQgJmxlOyAyNTApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQyYjhcdWI5YWNcdWM3NTggXHVkMDZjXHVhZTMwIG4gKDEgJmxlOyBuICZsZTsgNTAwMDAwKVx1YWNmYyBtICgyICZsZTsgbSAmbGU7IDEwPHN1cD45PFwvc3VwPilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgbi0xXHVhYzFjIFx1YzkwNFx1Yzc1OCBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBpKzFcdWJjODggXHVjODE1XHVjODEwXHVjNzU4IFx1YmQ4MFx1YmFhOFx1Yzc1OCBcdWJjODhcdWQ2MzggcChpKzEpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBwKGkrMSkgJmxlOyBpKSAxXHViYzg4IFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVkMmI4XHViOWFjXHVjNzU4IFx1YjhlOFx1ZDJiOFx1Yzc3NFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCA1ME1CXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVkNzk5XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgOFx1YWMwMFx1YzljMFx1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2hlYXAucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjA3cHg7IHdpZHRoOjQ4MHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3ODg5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ291bnRpbmcgaGVhcHMiLCJkZXNjcmlwdGlvbiI6IjxwPldlIGFyZSBnaXZlbiBhIHJvb3RlZCB0cmVlIG9mIG4gdmVydGljZXMuIFRoZSB2ZXJ0aWNlcyBhcmUgdG8gYmUgbGFiZWxlZCB3aXRoIG51bWJlcnMgMSwyLC4uLixuIHNvIHRoYXQgZWFjaCBsYWJlbCBpcyB1bmlxdWUgYW5kIHRoZSBoZWFwIGNvbmRpdGlvbiBob2xkcywgaS5lLiB0aGUgbGFiZWwgb2YgYW55IHZlcnRleCBpcyBsZXNzIHRoYW4gdGhlIGxhYmVsIG9mIGl0cyBwYXJlbnQuIEhvdyBtYW55IHN1Y2ggbGFiZWxsaW5ncyBleGlzdD8gU2luY2UgdGhpcyBudW1iZXIgbWF5IGJlIHF1aXRlIGxhcmdlLCBjYWxjdWxhdGUgb25seSBpdHMgcmVtYWluZGVyIG1vZHVsbyBtLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdHJlZSBkZXNjcmlwdGlvbnMuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgaW5wdXQgdHJlZXMgdCAodCAmbGU7IDI1MCkuIEVhY2ggdHJlZSBkZXNjcmlwdGlvbiBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0aGUgc2l6ZSBvZiB0aGUgdHJlZSBuICgxICZsZTsgbiAmbGU7IDUwMDAwMCkgYW5kIGFuIGludGVnZXIgbSAoMiAmbGU7IG0gJmxlOyAxMDxzdXA+OTxcL3N1cD4pLiBuICZuYnNwOzEgbGluZXMgZm9sbG93LCBpLXRoIG9mIHdoaWNoIGNvbnRhaW5zIHAoaSArIDEpLCB0aGUgbnVtYmVyIG9mIHRoZSBwYXJlbnQgb2YgdGhlIGkgKyAxLXRoIHZlcnRleCAoMSAmbGU7IHAoaSArIDEpICZsZTsgaSkuIFZlcnRleCBudW1iZXIgMSB3aWxsIGJlIHRoZSByb290IGluIGVhY2ggdHJlZSwgc28gaXRzIHBhcmVudCB3aWxsIG5vdCBiZSBnaXZlbi4gVG90YWwgc2l6ZSBvZiB0aGUgaW5wdXQgd2lsbCBub3QgZXhjZWVkIDUwTUIuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdHJlZSBvdXRwdXQgdGhlIG51bWJlciBvZiBpdHMgdmFsaWQgbGFiZWxsaW5ncyBtb2R1bG8gZ2l2ZW4gbS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSA4IHBvc3NpYmxlIGxhYmVsbGluZ3MgZnJvbSB0aGUgbGFzdCBleGFtcGxlIHRlc3QgY2FzZSBhcmUgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jaGVhcC5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDdweDsgd2lkdGg6NDgwcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=