시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB99221536.585%

문제

n개의 정점으로 이루어진 루트가 있는 트리가 주어진다. 각 정점에는 1번부터 n번까지 번호가 매겨져 있다. 같은 번호를 가지는 정점은 없고, 힙을 형성하고 있다. 즉, 각 정점에 붙여있는 숫자는 부모의 정점에 붙어잇는 숫자보다 작다. 이렇게 번호를 붙이는 방법의 수를 구하는 프로그램을 작성하시오. 이 수는 매우 클 수 있기 때문에, m으로 나눈 나머지를 출력한다.

입력

입력의 첫째 줄에는 테스트 케이스의 개수 t (t ≤ 250)가 주어진다. 각 테스트 케이스의 첫째 줄에는 트리의 크기 n (1 ≤ n ≤ 500000)과 m (2 ≤ m ≤ 109)이 주어진다. 다음 n-1개 줄의 i번째 줄에는 i+1번 정점의 부모의 번호 p(i+1)가 주어진다. (1 ≤ p(i+1) ≤ i) 1번 정점은 항상 트리의 루트이다. 입력의 크기는 50MB를 넘지 않는다.

출력

각 테스트 케이스에 대해서, 입력으로 주어지는 조건을 만족하는 힙의 개수를 출력한다.

예제 입력 1

4
3 1000000
1
1
4 1000000
1
1
1
5 1000000
1
2
3
4
5 1000000
1
1
3
3

예제 출력 1

2
6
1
8

힌트

마지막 예제의 경우에 아래와 같이 8가지가 가능하다.

W3sicHJvYmxlbV9pZCI6Ijc4ODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3OTkgXHVjMTM4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5uXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViOGU4XHVkMmI4XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWQyYjhcdWI5YWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjODE1XHVjODEwXHVjNWQwXHViMjk0IDFcdWJjODhcdWJkODBcdWQxMzAgblx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWIyOTQgXHVjODE1XHVjODEwXHVjNzQwIFx1YzVjNlx1YWNlMCwgXHVkNzk5XHVjNzQ0IFx1ZDYxNVx1YzEzMVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzk4OSwgXHVhYzAxIFx1YzgxNVx1YzgxMFx1YzVkMCBcdWJkOTlcdWM1ZWNcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViMjk0IFx1YmQ4MFx1YmFhOFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM1ZDAgXHViZDk5XHVjNWI0XHVjNzg3XHViMjk0IFx1YzIyYlx1Yzc5MFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWJjODhcdWQ2MzhcdWI5N2MgXHViZDk5XHVjNzc0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1Yzc3NCBcdWMyMThcdWIyOTQgXHViOWU0XHVjNmIwIFx1ZDA3NCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgbVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IHQgKHQgJmxlOyAyNTApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQyYjhcdWI5YWNcdWM3NTggXHVkMDZjXHVhZTMwIG4gKDEgJmxlOyBuICZsZTsgNTAwMDAwKVx1YWNmYyBtICgyICZsZTsgbSAmbGU7IDEwPHN1cD45PFwvc3VwPilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgbi0xXHVhYzFjIFx1YzkwNFx1Yzc1OCBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBpKzFcdWJjODggXHVjODE1XHVjODEwXHVjNzU4IFx1YmQ4MFx1YmFhOFx1Yzc1OCBcdWJjODhcdWQ2MzggcChpKzEpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBwKGkrMSkgJmxlOyBpKSAxXHViYzg4IFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVkMmI4XHViOWFjXHVjNzU4IFx1YjhlOFx1ZDJiOFx1Yzc3NFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCA1ME1CXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVkNzk5XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgOFx1YWMwMFx1YzljMFx1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2hlYXAucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjA3cHg7IHdpZHRoOjQ4MHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3ODg5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ291bnRpbmcgaGVhcHMiLCJkZXNjcmlwdGlvbiI6IjxwPldlIGFyZSBnaXZlbiBhIHJvb3RlZCB0cmVlIG9mIG4gdmVydGljZXMuIFRoZSB2ZXJ0aWNlcyBhcmUgdG8gYmUgbGFiZWxlZCB3aXRoIG51bWJlcnMgMSwyLC4uLixuIHNvIHRoYXQgZWFjaCBsYWJlbCBpcyB1bmlxdWUgYW5kIHRoZSBoZWFwIGNvbmRpdGlvbiBob2xkcywgaS5lLiB0aGUgbGFiZWwgb2YgYW55IHZlcnRleCBpcyBsZXNzIHRoYW4gdGhlIGxhYmVsIG9mIGl0cyBwYXJlbnQuIEhvdyBtYW55IHN1Y2ggbGFiZWxsaW5ncyBleGlzdD8gU2luY2UgdGhpcyBudW1iZXIgbWF5IGJlIHF1aXRlIGxhcmdlLCBjYWxjdWxhdGUgb25seSBpdHMgcmVtYWluZGVyIG1vZHVsbyBtLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdHJlZSBkZXNjcmlwdGlvbnMuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgaW5wdXQgdHJlZXMgdCAodCAmbGU7IDI1MCkuIEVhY2ggdHJlZSBkZXNjcmlwdGlvbiBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0aGUgc2l6ZSBvZiB0aGUgdHJlZSBuICgxICZsZTsgbiAmbGU7IDUwMDAwMCkgYW5kIGFuIGludGVnZXIgbSAoMiAmbGU7IG0gJmxlOyAxMDxzdXA+OTxcL3N1cD4pLiBuICZuYnNwOzEgbGluZXMgZm9sbG93LCBpLXRoIG9mIHdoaWNoIGNvbnRhaW5zIHAoaSArIDEpLCB0aGUgbnVtYmVyIG9mIHRoZSBwYXJlbnQgb2YgdGhlIGkgKyAxLXRoIHZlcnRleCAoMSAmbGU7IHAoaSArIDEpICZsZTsgaSkuIFZlcnRleCBudW1iZXIgMSB3aWxsIGJlIHRoZSByb290IGluIGVhY2ggdHJlZSwgc28gaXRzIHBhcmVudCB3aWxsIG5vdCBiZSBnaXZlbi4gVG90YWwgc2l6ZSBvZiB0aGUgaW5wdXQgd2lsbCBub3QgZXhjZWVkIDUwTUIuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdHJlZSBvdXRwdXQgdGhlIG51bWJlciBvZiBpdHMgdmFsaWQgbGFiZWxsaW5ncyBtb2R1bG8gZ2l2ZW4gbS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSA4IHBvc3NpYmxlIGxhYmVsbGluZ3MgZnJvbSB0aGUgbGFzdCBleGFtcGxlIHRlc3QgY2FzZSBhcmUgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jaGVhcC5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDdweDsgd2lkdGg6NDgwcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Central European Regional Contest > CERC 2008 I번

  • 문제의 오타를 찾은 사람: bachjs
  • 문제를 번역한 사람: baekjoon