시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB17131386.667%

문제

세 정수 $A_1$, $A_2$, $A_3$이 주어질 때, 다음 조건을 만족하는 루트 있는 이진 트리의 개수를 구하라.

  • 차수가 $1$인 정점의 개수가 $A_1$개, 차수가 $2$인 정점의 개수가 $A_2$개, 차수가 $3$인 정점의 개수가 $A_3$개이다.

이때 루트 있는 이진 트리는 좌/우 자식을 구분하며, 정점에는 번호가 부여되지 않는다.

두 루트 있는 이진 트리가 서로 다르게 세어질 조건은 다음과 같은 정점이 하나 이상 있는 경우이다.

  1. 한 트리의 루트에서 그 트리의 어떤 다른 정점까지 가기 위한 좌/우 순서열을 기록한다.
  2. 다른 트리에서 해당 순서로 이동했을 때, 해당 위치에 정점이 없다.

예시로, 다음 두 트리를 보자.

왼쪽 트리 A 오른쪽 트리 B

두 트리 모두 $(A_1,A_2,A_3) =(3,4,1)$인 트리이다. 두 트리의 루트는 $R$로 표기되어 있다. 왼쪽 트리는 왼쪽 $\rightarrow$ 오른쪽 $\rightarrow$ 왼쪽 경로를 따라갔을 때 정점 $x$가 있지만, 오른쪽 트리는 해당 경로를 따라갔을 때 도달하는 정점이 없기 때문에 서로 다른 트리로 세어진다.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\leq T\leq 100\, 000)$

다음 $T$개의 줄에 걸쳐 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되며, 세 정수 $A_1,A_2,A_3$가 공백으로 구분되어 주어진다. $(0\leq A_1,A_2,A_3\leq 1\, 000\, 000;A_1+A_2+A_3>0)$

출력

각 테스트 케이스마다 한 줄에 문제에서 요구하는 트리의 개수를 $998\, 244\, 353$으로 나눈 나머지를 출력한다.

예제 입력 1

5
2 0 0
2 1 0
3 1 1
4 3 3
6 0 4

예제 출력 1

2
5
14
0
28

예제 입력 2

2
3 4 1
3 5 1

예제 출력 2

800
2464
W3sicHJvYmxlbV9pZCI6IjM1NDc4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkM2VjXHViMmM5XHVjMmE0XHVjNzU4IFx1ZDJiOFx1YjlhYyBcdWMxMzhcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEzOCBcdWM4MTVcdWMyMTggJEFfMSQsICRBXzIkLCAkQV8zJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWIyZTRcdWM3NGMgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWI4ZThcdWQyYjggXHVjNzg4XHViMjk0IFx1Yzc3NFx1YzljNCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1Yjc3Yy48XC9wPlxyXG5cclxuPHVsPlxyXG48bGk+XHVjYzI4XHVjMjE4XHVhYzAwICQxJFx1Yzc3OCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwICRBXzEkXHVhYzFjLCBcdWNjMjhcdWMyMThcdWFjMDAgJDIkXHVjNzc4IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgJEFfMiRcdWFjMWMsIFx1Y2MyOFx1YzIxOFx1YWMwMCAkMyRcdWM3NzggXHVjODE1XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCAkQV8zJFx1YWMxY1x1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMgXHViOGU4XHVkMmI4IFx1Yzc4OFx1YjI5NCBcdWM3NzRcdWM5YzQgXHVkMmI4XHViOWFjXHViMjk0IFx1Yzg4Y1wvXHVjNmIwIFx1Yzc5MFx1YzJkZFx1Yzc0NCBcdWFkNmNcdWJkODRcdWQ1NThcdWJhNzAsIFx1YzgxNVx1YzgxMFx1YzVkMFx1YjI5NCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDgwXHVjNWVjXHViNDE4XHVjOWMwIDxzdHJvbmc+XHVjNTRhXHViMjk0XHViMmU0PFwvc3Ryb25nPi48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YjhlOFx1ZDJiOCBcdWM3ODhcdWIyOTQgXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHVhYzhjIFx1YzEzOFx1YzViNFx1YzljOCBcdWM4NzBcdWFjNzRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWM4MTBcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMSBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcbjxsaT5cdWQ1NWMgXHVkMmI4XHViOWFjXHVjNzU4IFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyBcdWFkZjggXHVkMmI4XHViOWFjXHVjNzU4IFx1YzViNFx1YjVhNCBcdWIyZTRcdWI5NzggXHVjODE1XHVjODEwXHVhZTRjXHVjOWMwIFx1YWMwMFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjODhjXC9cdWM2YjAgXHVjMjFjXHVjMTFjXHVjNWY0XHVjNzQ0IFx1YWUzMFx1Yjg1ZFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPGxpPlx1YjJlNFx1Yjk3OCBcdWQyYjhcdWI5YWNcdWM1ZDBcdWMxMWMgXHVkNTc0XHViMmY5IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWQ1NzRcdWIyZjkgXHVjNzA0XHVjZTU4XHVjNWQwIFx1YzgxNVx1YzgxMFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNjA4XHVjMmRjXHViODVjLCBcdWIyZTRcdWM3NGMgXHViNDUwIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxkaXYgc3R5bGU9XCJkaXNwbGF5OiBmbGV4OyBqdXN0aWZ5LWNvbnRlbnQ6IGNlbnRlcjsgd2lkdGg6IDEwMCU7XCI+XHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJib3JkZXItY29sbGFwc2U6IGNvbGxhcHNlOyBib3JkZXI6IDFweCBzb2xpZCBibGFjazsgd2lkdGg6IDYwMHB4OyB0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHJcbjx0Ym9keT5cclxuPHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJib3JkZXI6IDFweCBzb2xpZCBibGFjazsgcGFkZGluZzogMTBweDsgd2lkdGg6IDI5OXB4O1wiPjxpbWcgYWx0PVwiXHVjNjdjXHVjYWJkIFx1ZDJiOFx1YjlhYyBBXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNTgyMTMzNzAtZDYzYy00NzJkLWExM2EtYjgyOWZjZDBjY2IzXC9cIiBzdHlsZT1cIm1heC13aWR0aDogMTAwJTsgaGVpZ2h0OiBhdXRvO1wiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJib3JkZXI6IDFweCBzb2xpZCBibGFjazsgcGFkZGluZzogMTBweDsgd2lkdGg6IDM1MXB4O1wiPjxpbWcgYWx0PVwiXHVjNjI0XHViOTc4XHVjYWJkIFx1ZDJiOFx1YjlhYyBCXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvOGRkYWM0MGQtNmVkZC00YTY0LTk3MTUtZjNmM2U5YzRjMzZmXC9cIiBzdHlsZT1cIm1heC13aWR0aDogMTAwJTsgaGVpZ2h0OiBhdXRvO1wiIFwvPjxcL3RkPlxyXG48XC90cj5cclxuPFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG48XC9kaXY+XHJcblxyXG48cD5cdWI0NTAgXHVkMmI4XHViOWFjIFx1YmFhOFx1YjQ1MCAkKEFfMSxBXzIsQV8zKSA9KDMsNCwxKSRcdWM3NzggXHVkMmI4XHViOWFjXHVjNzc0XHViMmU0LiBcdWI0NTAgXHVkMmI4XHViOWFjXHVjNzU4IFx1YjhlOFx1ZDJiOFx1YjI5NCAkUiRcdWI4NWMgXHVkNDVjXHVhZTMwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjNjdjXHVjYWJkIFx1ZDJiOFx1YjlhY1x1YjI5NCBcdWM2N2NcdWNhYmQgJFxccmlnaHRhcnJvdyQgXHVjNjI0XHViOTc4XHVjYWJkICRcXHJpZ2h0YXJyb3ckIFx1YzY3Y1x1Y2FiZCBcdWFjYmRcdWI4NWNcdWI5N2MgXHViNTMwXHViNzdjXHVhYzE0XHVjNzQ0IFx1YjU0YyBcdWM4MTVcdWM4MTAgJHgkXHVhYzAwIFx1Yzc4OFx1YzljMFx1YjljYywgXHVjNjI0XHViOTc4XHVjYWJkIFx1ZDJiOFx1YjlhY1x1YjI5NCBcdWQ1NzRcdWIyZjkgXHVhY2JkXHViODVjXHViOTdjIFx1YjUzMFx1Yjc3Y1x1YWMxNFx1Yzc0NCBcdWI1NGMgXHViM2M0XHViMmVjXHVkNTU4XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc3NCBcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVkMmI4XHViOWFjXHViODVjIFx1YzEzOFx1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggJFQkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxXFxsZXEgVFxcbGVxIDEwMFxcLCAwMDApJDxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJFQkXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHViYTcwLCBcdWMxMzggXHVjODE1XHVjMjE4ICRBXzEsQV8yLEFfMyRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMFxcbGVxIEFfMSxBXzIsQV8zXFxsZXEgMVxcLCAwMDBcXCwgMDAwO0FfMStBXzIrQV8zJmd0OzApJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzY5NFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjICQ5OThcXCwgMjQ0XFwsIDM1MyRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzU0NzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQb25peCBDb3VudHMgVHJlZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIHRocmVlIGludGVnZXJzICRBXzEkLCAkQV8yJCwgYW5kICRBXzMkLCBmaW5kIHRoZSBudW1iZXIgb2Ygcm9vdGVkIGJpbmFyeSB0cmVlcyBzYXRpc2Z5aW5nIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9uLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBudW1iZXIgb2YgdmVydGljZXMgb2YgZGVncmVlICQxJCBpcyAkQV8xJCwgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBvZiBkZWdyZWUgJDIkIGlzICRBXzIkLCBhbmQgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBvZiBkZWdyZWUgJDMkIGlzICRBXzMkLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkhlcmUsIGluIGEgcm9vdGVkIGJpbmFyeSB0cmVlLCBsZWZ0IGFuZCByaWdodCBjaGlsZHJlbiBhcmUgZGlzdGluZ3Vpc2hlZCwgYW5kIHRoZSB2ZXJ0aWNlcyBhcmUgPHN0cm9uZz5ub3Q8XC9zdHJvbmc+IGxhYmVsZWQuPFwvcD5cclxuXHJcbjxwPlR3byByb290ZWQgYmluYXJ5IHRyZWVzIGFyZSBjb3VudGVkIGFzIGRpZmZlcmVudCB3aGVuIHRoZXJlIGV4aXN0cyBhdCBsZWFzdCBvbmUgdmVydGV4IHNhdGlzZnlpbmcgdGhlIGZvbGxvd2luZy48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5SZWNvcmQgdGhlIHNlcXVlbmNlIG9mIGxlZnRcL3JpZ2h0IG1vdmVzIG5lZWRlZCB0byBnbyBmcm9tIHRoZSByb290IG9mIG9uZSB0cmVlIHRvIGFub3RoZXIgdmVydGV4IGluIHRoYXQgdHJlZS48XC9saT5cclxuXHQ8bGk+SW4gdGhlIG90aGVyIHRyZWUsIGlmIHlvdSBmb2xsb3cgdGhlIHNhbWUgc2VxdWVuY2UsIHRoZXJlIGlzIG5vIHZlcnRleCBhdCB0aGF0IHBvc2l0aW9uLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBjb25zaWRlciB0aGUgZm9sbG93aW5nIHR3byB0cmVlcy48XC9wPlxyXG5cclxuPGRpdiBzdHlsZT1cImRpc3BsYXk6IGZsZXg7IGp1c3RpZnktY29udGVudDogY2VudGVyOyB3aWR0aDogMTAwJTtcIj5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cImJvcmRlci1jb2xsYXBzZTogY29sbGFwc2U7IGJvcmRlcjogMXB4IHNvbGlkIGJsYWNrOyB3aWR0aDogNjAwcHg7IHRleHQtYWxpZ246IGNlbnRlcjtcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cImJvcmRlcjogMXB4IHNvbGlkIGJsYWNrOyBwYWRkaW5nOiAxMHB4OyB3aWR0aDogMjk5cHg7XCI+PGltZyBhbHQ9XCJcdWM2N2NcdWNhYmQgXHVkMmI4XHViOWFjIEFcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC81ODIxMzM3MC1kNjNjLTQ3MmQtYTEzYS1iODI5ZmNkMGNjYjNcL1wiIHN0eWxlPVwibWF4LXdpZHRoOiAxMDAlOyBoZWlnaHQ6IGF1dG87XCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cImJvcmRlcjogMXB4IHNvbGlkIGJsYWNrOyBwYWRkaW5nOiAxMHB4OyB3aWR0aDogMzUxcHg7XCI+PGltZyBhbHQ9XCJcdWM2MjRcdWI5NzhcdWNhYmQgXHVkMmI4XHViOWFjIEJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC84ZGRhYzQwZC02ZWRkLTRhNjQtOTcxNS1mM2YzZTljNGMzNmZcL1wiIHN0eWxlPVwibWF4LXdpZHRoOiAxMDAlOyBoZWlnaHQ6IGF1dG87XCIgXC8+PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcbjxcL2Rpdj5cclxuXHJcbjxwPkJvdGggdHJlZXMgc2F0aXNmeSAkKEFfMSxBXzIsQV8zKSA9KDMsNCwxKSQuIFRoZSByb290cyBvZiB0aGUgdHdvIHRyZWVzIGFyZSBsYWJlbGVkICRSJC4gSW4gdGhlIGxlZnQgdHJlZSwgdGhlcmUgaXMgYSB2ZXJ0ZXggJHgkIGFsb25nIHRoZSBwYXRoIGxlZnQgJFxccmlnaHRhcnJvdyQgcmlnaHQgJFxccmlnaHRhcnJvdyQgbGVmdCwgYnV0IGluIHRoZSByaWdodCB0cmVlIHRoZXJlIGlzIG5vIHZlcnRleCBhbG9uZyB0aGF0IHBhdGgsIHNvIHRoZSB0d28gdHJlZXMgYXJlIGNvdW50ZWQgYXMgZGlmZmVyZW50LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzICRUJC4gJCgxXFxsZXEgVFxcbGVxIDEwMFxcLCAwMDApJDxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0ICRUJCBsaW5lcyBjb250YWlucyBvbmUgdGVzdCBjYXNlLiBFYWNoIHRlc3QgY2FzZSBjb250YWlucyB0aHJlZSBpbnRlZ2VycyAkQV8xLCBBXzIsIEFfMyQsIHNlcGFyYXRlZCBieSBzcGFjZXMuICQoMCBcXGxlcSBBXzEsIEFfMiwgQV8zIFxcbGVxIDFcXCwwMDBcXCwwMDA7IEFfMSArIEFfMiArIEFfMyAmZ3Q7IDApJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSBudW1iZXIgb2Ygcm9vdGVkIGJpbmFyeSB0cmVlcyBkZXNjcmliZWQgaW4gdGhlIHByb2JsZW0sIG1vZHVsbyAkOTk4XFwsMjQ0XFwsMzUzJCwgb25lIHBlciBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=