복도와 집사

도니는 성공한 사업가이고 거대한 저택을 소유하고 있다. 이 저택에는 1번부터 N번까지 번호가 붙은 N개의 방이 N − 1개의 복도로 연결되어 있고, 어떤 방에서든 복도를 따라가면 다른 모든 방에 도달할 수 있다. i번째 복도는 ui번 방과 vi번 방을 연결하며, 더러움 정도는 짝수인 정수 wi이다.

부유함에도 불구하고 도니에게는 청소기가 하나뿐이고, 처음에 1번 방에 놓여 있다. 도니의 집사인 당신은 모든 복도를 청소하려고 한다. 복도 하나를 청소할 때는 청소기를 복도의 한쪽 끝에서 다른 쪽 끝까지 움직인다. 예를 들어 i번째 복도에 청소기를 움직이려면 ui번 방에서 출발해 vi번 방에서 멈추거나, vi번 방에서 출발해 ui번 방에서 멈출 수 있다. 더러움 정도가 w인 복도는 청소기가 정확히 w번 지나가야 한다.

(청소를 1번 방에서 시작하고 1번 방에서 마친다고 할 때) 모든 복도를 청소하는 방법은 몇 가지인가? 두 방법은, 두 방법에서 청소기가 j번째로 지나간 복도가 서로 다른 정수 j가 존재하면 서로 다른 방법으로 본다.

다음은 N = 4개의 방과 3개의 복도로 이루어진 저택의 예이다.

• 1번째 복도는 1번 방과 2번 방을 연결하며 더러움 정도는 2이다.
• 2번째 복도는 1번 방과 3번 방을 연결하며 더러움 정도는 4이다.
• 3번째 복도는 3번 방과 4번 방을 연결하며 더러움 정도는 2이다.

이 예에서 모든 복도를 청소하는 방법은 다음 방들을 지나는 6가지이다.

• 1 → 2 → 1 → 3 → 1 → 3 → 4 → 3 → 1.
• 1 → 2 → 1 → 3 → 4 → 3 → 1 → 3 → 1.
• 1 → 3 → 1 → 2 → 1 → 3 → 4 → 3 → 1.
• 1 → 3 → 1 → 3 → 4 → 3 → 1 → 2 → 1.
• 1 → 3 → 4 → 3 → 1 → 2 → 1 → 3 → 1.
• 1 → 3 → 4 → 3 → 1 → 3 → 1 → 2 → 1.

각 방법에서 1번 방과 2번 방을 연결하는 복도는 2번, 1번 방과 3번 방을 연결하는 복도는 4번, 3번 방과 4번 방을 연결하는 복도는 2번 지나간다.

입력은 정수 N (2 ≤ N ≤ 10 000)이 있는 한 줄로 시작한다. N은 방의 수이다. 다음 N − 1개 줄에는 각각 세 정수 ui vi wi (1 ≤ ui, vi ≤ N; 2 ≤ wi ≤ 200; wi는 짝수)가 주어지며, 복도가 연결하는 방과 그 더러움 정도를 나타낸다. 어떤 방에서든 복도를 따라가면 다른 모든 방에 도달할 수 있음이 보장된다.

모든 복도를 청소하는 방법의 수를 998 244 353으로 나눈 나머지를 한 줄에 출력한다.