Tương truyền ở vương quốc bóng đêm có một cây cầu vồng gồm $n$ nút. Cây cầu vồng là một cây có gốc, các nút được đánh số $0\sim n-1$, trong đó nút $0$ là gốc; cha của nút $i$ ($1\le i<n$) là $f_i$.

Mỗi nút trên cây cầu vồng có thể hiện ra bất kỳ màu nào. Có vô hạn màu, nhưng độ rực rỡ của cây cầu vồng chỉ do số màu khác nhau xuất hiện trong mỗi cây con quyết định, không phụ thuộc vào màu cụ thể. Cụ thể, nếu cây con có gốc là nút $i$ ($0\le i<n$) có tổng cộng $c_i$ màu khác nhau trên các nút, thì độ rực rỡ của cây cầu vồng được biểu diễn bằng dãy $[c_0,c_1,\ldots,c_{n-1}]$. Chẳng hạn, trong hình dưới, các nút $0,1,5$ có màu xanh lam, các nút $2,4$ có màu đỏ, nút $3$ có màu vàng, nên độ rực rỡ của cây cầu vồng là $[3,2,1,2,1,1]$.

Sự thay đổi của các đám mây khiến màu sắc của cây cầu vồng tuân theo một quy luật nhất định. Cụ thể, mỗi quy luật được mô tả bởi một tập con các nút tương ứng $S\subseteq\{1,2,\ldots,n-1\}$: mỗi nút $u$ trong $S$ có cùng màu với một tổ tiên nào đó. Hình thức hóa, với mọi $u\in S$, tồn tại một tổ tiên $p$ của $u$ ($p\ne u$) sao cho $u$ và $p$ cùng màu. Dù bị ràng buộc bởi quy luật trên, cây cầu vồng vẫn có thể hiện ra các màu sắc khác nhau và tạo ra những độ rực rỡ khác nhau. Gọi $w_S$ là số loại độ rực rỡ của cây cầu vồng thỏa mãn quy luật $S$; hai độ rực rỡ khác nhau khi và chỉ khi hai dãy khác nhau ở ít nhất một phần tử.

Hãy tính tổng số loại độ rực rỡ thỏa mãn từng quy luật trên tất cả $2^{n-1}$ quy luật có thể, tức là $\sum_{S\subseteq\{1,2,\ldots,n-1\}}w_S$. Vì đáp án có thể lớn, chỉ cần tìm phần dư khi chia cho $998\,244\,353$.

Chi tiết cài đặt

Thí sinh không cần và cũng không nên cài đặt hàm main.

Thí sinh phải bảo đảm mã nguồn nộp có tệp tiêu đề rainbow.h, tức là thêm đoạn mã sau ở đầu chương trình:

#include "rainbow.h"

Thí sinh cần cài đặt hàm sau trong tệp mã nguồn rainbow.cpp được nộp:

int rainbow(int c, int n, std::vector<int> f);

• $c,n$ lần lượt biểu thị số hiệu bộ kiểm thử và số nút của cây cầu vồng. $c=0$ biểu thị bộ kiểm thử ví dụ.
• $f$ là một dãy có độ dài $n$, trong đó $f_0=0$, còn $f_i$ ($1\le i<n$) là cha của nút $i$.
• Hàm cần trả về phần dư của tổng số loại độ rực rỡ của cây cầu vồng thỏa mãn từng quy luật khi chia cho $998\,244\,353$.
• Với mỗi bộ kiểm thử, hàm này sẽ được chương trình chấm gọi đúng một lần.

template_rainbow.cpp trong thư mục bài toán là mã ví dụ được cung cấp; thí sinh có thể tham khảo và cài đặt mã của mình.

Cách kiểm thử chương trình

Thí sinh có thể dùng lệnh sau trong thư mục bài toán để biên dịch thành tệp thực thi:

g++ grader.cpp rainbow.cpp -o rainbow -O2 -std=c++14 -static

Đối với tệp thực thi rainbow đã biên dịch:

• Tệp thực thi đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

  • Dòng đầu tiên chứa hai số nguyên không âm $c,n$.
  • Dòng thứ hai chứa $n-1$ số nguyên không âm $f_1,f_2,\ldots,f_{n-1}$.

• Tệp thực thi ghi dữ liệu ra đầu ra chuẩn theo định dạng sau:

  • Xuất một dòng chứa một số nguyên không âm biểu thị giá trị trả về của hàm rainbow.

Ví dụ

Dữ liệu vào 1

0 3
0 0

Dữ liệu ra 1

8

Ghi chú

• Với quy luật $S=\varnothing$, cây cầu vồng có ba loại độ rực rỡ: $[1,1,1]$, $[2,1,1]$, $[3,1,1]$;
• Với quy luật $S=\{1\}$, cây cầu vồng có hai loại độ rực rỡ: $[1,1,1]$, $[2,1,1]$;
• Với quy luật $S=\{2\}$, cây cầu vồng có hai loại độ rực rỡ: $[1,1,1]$, $[2,1,1]$;
• Với quy luật $S=\{1,2\}$, cây cầu vồng có một loại độ rực rỡ: $[1,1,1]$.

Vì vậy, đáp án là $3+2+2+1=8$.

Dữ liệu vào 2

0 6
0 1 0 3 1

Dữ liệu ra 2

279

Ví dụ 3

Xem rainbow/rainbow3.in và rainbow/rainbow3.ans trong thư mục của thí sinh.

Ví dụ này thỏa mãn giới hạn của các bộ kiểm thử $3,4$.

Ví dụ 4

Xem rainbow/rainbow4.in và rainbow/rainbow4.ans trong thư mục của thí sinh.

Ví dụ này thỏa mãn giới hạn của các bộ kiểm thử $5\sim7$.

Ví dụ 5

Xem rainbow/rainbow5.in và rainbow/rainbow5.ans trong thư mục của thí sinh.

Ví dụ này thỏa mãn giới hạn của các bộ kiểm thử $8,9$.

Ví dụ 6

Xem rainbow/rainbow6.in và rainbow/rainbow6.ans trong thư mục của thí sinh.

Ví dụ này thỏa mãn giới hạn của các bộ kiểm thử $10\sim12$.

Giới hạn

Với mọi dữ liệu kiểm thử:

• $1\le n\le200$;
• Với mọi $1\le i<n$, $0\le f_i<i$.

Tính chất đặc biệt A: với mọi $1\le i<n$, $f_i=i-1$.

Tính chất đặc biệt B: với mọi $0\le i<n$, có nhiều nhất hai giá trị $j$ thỏa mãn $f_j=i$.