Đánh dấu trên cây

Đề bài

Cho một cây \(T\) gồm \(N\) đỉnh được gán nhãn từ \(1\) đến \(N\). Ta có \(2\) quân cờ:

• Quân cờ \(A\) ban đầu ở đỉnh \(1\).
• Quân cờ \(B\) ban đầu ở đỉnh \(N\).

Trong mỗi bước, bạn được phép di chuyển đúng một trong hai quân cờ từ đỉnh hiện tại sang một đỉnh kề (tức là hai đỉnh có cạnh nối trực tiếp).

Một đỉnh được coi là đã thăm nếu tại một thời điểm nào đó có ít nhất một trong hai quân cờ đứng trên đỉnh đó.

Với một tập con \(S\) bất kỳ của các đỉnh, ta định nghĩa \(f(S)\) là số bước ít nhất cần thực hiện để:

• Tất cả các đỉnh trong \(S\) đều được thăm (có thể thăm thêm các đỉnh không thuộc \(S\) hoặc không, không bắt buộc).
• Sau cùng, hai quân cờ quay về vị trí ban đầu: quân \(A\) ở đỉnh \(1\) và quân \(B\) ở đỉnh \(N\).

Lưu ý:

• Với \(S = \varnothing\) (tập rỗng) hoặc \(S = {1, N}\) thì luôn có \(f(S) = 0\), vì:
  • Tập rỗng không có đỉnh nào cần thăm.
  • Hai đỉnh \(1\) và \(N\) đã được coi là thăm ngay từ thời điểm ban đầu.

Bạn được cho một cây gồm \(N\) đỉnh. Hãy tính giá trị:

tức là tổng \(f(S)\) trên tất cả \(2^N\) tập con \(S\) của tập đỉnh. Vì kết quả có thể rất lớn, hãy in ra kết quả theo modulo \(998244353\).

Cây được cho dưới dạng dãy \(par_2, par_3, \dots, par_N\) sao cho \(1 \le par_i < i\) và với mỗi \(2 \le i \le N\) có một cạnh nối giữa \((par_i, i)\).

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(T\) — số lượng bộ test.
• Với mỗi test:
  • Dòng thứ nhất chứa một số nguyên \(N\) — số lượng đỉnh của cây.
  • Dòng thứ hai chứa \(N-1\) số nguyên \(par_2, par_3, \dots, par_N\), trong đó:
    • \(1 \le par_i < i\),
    • tồn tại cạnh nối giữa các đỉnh \(par_i\) và \(i\).

Dữ liệu ra

Với mỗi test, in ra một dòng chứa một số nguyên là:

Ràng buộc

• \(1 \le T \le 2500\)
• \(2 \le N \le 5000\)
• \(1 \le par_i < i\) với mọi \(2 \le i \le N\)
• Tổng \(N\) trên tất cả các test không vượt quá \(5000\).

Sample Input 1

5
2
1
3
1 2
5
1 2 1 3
7
1 2 1 4 4 2
6
1 2 3 4 5

Sample Output 1

0
8
96
800
296

Giải thích

• Test 1: Cây chỉ có hai đỉnh \(1\) và \(2\), ban đầu \(A\) ở \(1\), \(B\) ở \(2\). Dễ thấy với mọi tập con \(S\), luôn có thể thỏa điều kiện mà không cần di chuyển (hoặc không thể giảm hơn \(0\)). Do đó, với mọi \(S\) ta có \(f(S) = 0\), nên tổng bằng \(0\).

• Test 2: Cây là đường \(1 - 2 - 3\) với \(A\) ở \(1\), \(B\) ở \(3\). Khi đó \(f(S) = 2\) nếu và chỉ nếu \(2 \in S\) (vì bắt buộc phải cho ít nhất một quân cờ đi qua đỉnh \(2\) rồi quay về), còn nếu \(2 \notin S\) thì luôn có thể không di chuyển bước nào, nên \(f(S) = 0\). Có \(4\) tập con \(S\) chứa \(2\) nên tổng là \(4 \times 2 = 8\). Các test khác tương tự, theo định nghĩa của \(f(S)\).