久莲 là một cô gái thích ra đề.

Sau World Final năm nay, 久莲 đặc biệt yêu thích hình học tính toán, vì thế cô định ra một bài hình học tính toán trong kỳ thi NOI: đây là một bài toán mà chỉ có tên bài liên quan đến hình học tính toán.

Trước hết, 久莲 cho một cây có gốc $T$ gồm $n$ ($n\ge2$) nút, nút gốc được đánh số $1$. Định nghĩa các nút lá là tất cả những nút ngoài gốc có bậc đúng bằng $1$. Hình dưới là một ví dụ về cây $T$, trong đó tập các nút lá là $\{3,4,5\}$.

Tiếp theo, từ cây này, 久莲 xây dựng một dãy $A$:

• Bắt đầu từ gốc, duyệt toàn bộ cây theo chiều sâu; khi duyệt, thăm các nút con theo thứ tự số hiệu tăng dần. Như vậy thu được thứ tự DFS của cây $T$.
• Sau đó, theo thứ tự xuất hiện từ trước đến sau trong thứ tự DFS, 久莲 xếp tất cả các nút lá thành một hàng để thu được dãy $A$.

Hơn nữa, qua dãy $A$, 久莲 định nghĩa khoảng cách $d(u,v)$ giữa hai nút lá $u,v$: giả sử $u$ là phần tử thứ $i$ trong $A$ và $v$ là phần tử thứ $j$, thì $d(u,v)=\min(|i-j|,|A|-|i-j|)$. Trong đó, $|A|$ là độ dài dãy, tức là số lá của $T$; $i,j$ chỉ vị trí xuất hiện, được đếm từ $1$.

Trong ví dụ trên, dãy $A$ là $[4,5,3]$, với $d(3,5)=d(3,4)=d(4,5)=1$; vị trí xuất hiện của $3,4,5$ lần lượt là $3,1,2$.

Cuối cùng, 久莲 cho một tham số $K$. Từ cây có gốc $T$ và dãy $A$, ta có thể xây dựng một đồ thị vô hướng $G$ có $n$ đỉnh, không có cạnh bội và không có khuyên: giữa hai đỉnh khác nhau $u,v$ có cạnh khi và chỉ khi thỏa mãn ít nhất một trong các điều kiện sau:

• Trong cây $T$ có cạnh nối $u,v$.
• Trong cây $T$, cả $u,v$ đều là nút lá và $d(u,v)\le K$.

Khi $K=1$ hoặc $2$, đồ thị $G$ thu được từ ví dụ trên đều như hình dưới đây:

Bây giờ, 久莲 muốn bạn tính xem có bao nhiêu chu trình Hamilton khác nhau trong $G$. Đáp án có thể rất lớn, hãy xuất phần dư khi chia cho $998244353$.

Dưới đây là một số định nghĩa bổ sung:

• Một chu trình Hamilton $H$ của đồ thị vô hướng $G$ không có cạnh bội và khuyên là một tập con các cạnh của $G$, trong đó mỗi đỉnh có đúng hai cạnh kề khác nhau thuộc $H$, và từ bất kỳ đỉnh nào cũng có thể đi trực tiếp hoặc gián tiếp đến bất kỳ đỉnh khác qua các cạnh của $H$.
• Hai chu trình Hamilton $H_1,H_2$ của đồ thị vô hướng $G$ không có cạnh bội và khuyên là khác nhau khi và chỉ khi tồn tại một cạnh $e$ sao cho $e$ thuộc $H_1$ và không thuộc $H_2$.

Dữ liệu vào

Đọc dữ liệu từ tệp polygon.in.

Dòng đầu tiên chứa hai số nguyên $n,K$, biểu thị số nút của cây $T$ và tham số $K$ mà 久莲 chọn.

Dòng thứ hai chứa $n-1$ số nguyên $f_i$ ($1\le f_i\le i$), trong đó $f_i$ biểu thị rằng trên cây $T$ có cạnh $(f_i,i+1)$.

Dữ liệu ra

Ghi kết quả vào tệp polygon.out.

Xuất một dòng chứa một số nguyên, biểu thị phần dư của số chu trình Hamilton khi chia cho $998244353$.

Ví dụ

Dữ liệu vào 1

5 1
1 1 2 2

Dữ liệu ra 1

2

Ghi chú

Ví dụ này hoàn toàn giống với ví dụ trong đề bài. Thứ tự các nút đi qua của hai chu trình Hamilton lần lượt là $(1,2,4,5,3)$ và $(1,2,5,4,3)$.

Nhiệm vụ con

Kích thước dữ liệu và tính chất của từng bộ kiểm thử được cho trong bảng sau:

Trong đó, tính chất A bảo đảm mọi nút trên cây đều có nhiều nhất hai nút con.

Với mọi dữ liệu, bảo đảm $1\le f_i\le i$, $2\le n\le1000$.