Cây phả hệ

Trong Học viện mật mã, các nhà nghiên cứu đang làm việc với cấu trúc dữ liệu dạng cây phả hệ để bảo vệ thông tin. Cây phả hệ này có \(N\) nút, được đánh số từ \(1\) đến \(N\), với nút \(1\) là nút gốc.

Một nhà nghiên cứu trẻ tên là Kaito được giao nhiệm vụ phân tích một loại hoán vị "Tốt" trên cây.

Một hoán vị \(p_1, p_2, \dots, p_n\) được gọi là Tốt khi và chỉ khi, với mỗi vị trí \(i\) (\(1 \le i \le n\)), ít nhất một trong các điều kiện sau được thỏa mãn:

• Vị trí cố định: \(p_i = i\).
• Quan hệ Tổ Tiên: Nút \(p_i\) là tổ tiên của nút \(i\).
• Quan hệ Hậu Duệ: Nút \(p_i\) là hậu duệ của nút \(i\).

Bạn được yêu cầu giúp Kaito đếm số lượng hoán vị Tốt có độ dài \(N\) cho cây phả hệ đã cho, và in ra kết quả sau khi lấy modulo \(998\,244\,353\).

Input

• Dòng đầu tiên chứa số nguyên \(T\) (\(1 \le T \le 5\)) --- số lượng bộ dữ liệu thử nghiệm.

• Đối với mỗi bộ dữ liệu:

• Dòng đầu chứa số nguyên \(N\) (\(2 \le N \le 5\,000\)) --- số lượng nút trên cây.

• Dòng thứ hai chứa \(N - 1\) số nguyên \(a_2, a_3, \ldots, a_n\) (\(1 \le a_i \le i-1\)) --- \(a_i\) là cha trực tiếp của nút \(i\).

Output

Với mỗi bộ dữ liệu, in ra một số nguyên là số lượng hoán vị Tốt modulo \(998\,244\,353\).

Example

3
3
1 1
3
1 2
6
1 1 1 2 2

3
6
20

Scoring

• Subtask \(1\) (\(20\%\) số điểm) : \(N \leq 10\).
• Subtask \(2\) (\(20\%\) số điểm) : \(N \leq 20\).
• Subtask \(3\) (\(20\%\) số điểm) : \(a_i = 1\) với \(i = 2..N\) trong tất cả các bộ dữ liệu.
• Subtask \(4\) (\(20\%\) số điểm) : \(N \leq 100\).
• Subtask \(5\) (\(20\%\) số điểm) : không có ràng buộc gì thêm.