האגדה מספרת שבארץ הלילה צומח עץ קשת ובו $n$ צמתים. עץ הקשת הוא עץ מושרש שצמתיו ממוספרים מ־$0$ עד $n-1$. צומת $0$ הוא השורש, וההורה של צומת $i$ ($1\le i<n$) הוא $f_i$.

כל צומת בעץ הקשת יכול להופיע בכל צבע. יש אינסוף צבעים, אך מידת הצבעוניות של העץ נקבעת רק על פי מספר הצבעים השונים המופיעים בכל תת־עץ, ואינה תלויה בזהות הצבעים. באופן מפורט, אם בתת־העץ ששורשו בצומת $i$ ($0\le i<n$) מופיעים צמתים ב־$c_i$ צבעים שונים, אפשר לייצג את צבעוניות העץ בסדרה $[c_0,c_1,\ldots,c_{n-1}]$. למשל, באיור הבא הצמתים $0,1,5$ כחולים, הצמתים $2,4$ אדומים וצומת $3$ צהוב, ולכן צבעוניות העץ היא $[3,2,1,2,1,1]$.

שינויים בעננים גורמים לצבעי עץ הקשת לקיים חוק מסוים. כל חוק ניתן לתיאור באמצעות קבוצת צמתים $S\subseteq\{1,2,\ldots,n-1\}$: לכל צומת $u$ בקבוצה $S$ יש אותו צבע כמו לאחד מאבותיו. באופן פורמלי, לכל $u\in S$ קיים אב קדמון $p$ של $u$, כאשר $p\ne u$, שצבעו זהה לצבע $u$. למרות המגבלה הזאת, העץ עדיין יכול להופיע בצביעות שונות בעלות צבעוניות שונה. נסמן ב־$w_S$ את מספר ערכי הצבעוניות השונים של עצי קשת המקיימים את החוק $S$. שני ערכי צבעוניות שונים אם ורק אם לפחות איבר אחד שונה בשתי הסדרות.

חשבו, עבור כל $2^{n-1}$ החוקים האפשריים, את סכום מספרי ערכי הצבעוניות של עצי קשת המקיימים כל חוק, כלומר $\sum_{S\subseteq\{1,2,\ldots,n-1\}}w_S$. מאחר שהתשובה עשויה להיות גדולה, נדרשת רק השארית מודולו $998\,244\,353$.

פרטי מימוש

אין צורך לממש פונקציית main, ואין לעשות זאת.

עליכם לוודא שקובץ המקור המוגש כולל את קובץ הכותרת rainbow.h, כלומר להוסיף בתחילת התוכנית את הקוד הבא:

#include "rainbow.h"

עליכם לממש בקובץ המקור המוגש rainbow.cpp את הפונקציה הבאה:

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

• $c,n$ מציינים בהתאמה את מספר הבדיקה ואת מספר הצמתים בעץ הקשת. $c=0$ מציין שזו דוגמה.
• $f$ היא סדרה באורך $n$, שבה $f_0=0$, ו־$f_i$ ($1\le i<n$) הוא ההורה של צומת $i$.
• הפונקציה צריכה להחזיר את סכום מספרי ערכי הצבעוניות של עצי קשת המקיימים כל חוק, מודולו $998\,244\,353$.
• בכל בדיקה תוכנית הבדיקה תקרא לפונקציה בדיוק פעם אחת.

הקובץ template_rainbow.cpp בתיקיית הבעיה הוא קוד לדוגמה שסופק לעיונכם; תוכלו להיעזר בו כדי לממש את הקוד שלכם.

בדיקת התוכנית

אפשר להשתמש בפקודה הבאה בתיקיית הבעיה כדי להדר לקובץ הרצה:

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

עבור קובץ ההרצה rainbow שהתקבל:

• קובץ ההרצה קורא מהקלט הסטנדרטי נתונים בפורמט הבא:

  • השורה הראשונה מכילה שני מספרים שלמים אי־שליליים $c,n$.
  • השורה השנייה מכילה $n-1$ מספרים שלמים אי־שליליים $f_1,f_2,\ldots,f_{n-1}$.

• קובץ ההרצה כותב לפלט הסטנדרטי נתונים בפורמט הבא:

  • שורה אחת ובה מספר שלם אי־שלילי, הערך המוחזר מהפונקציה rainbow.

דוגמאות

קלט 1

0 3
0 0

פלט 1

8

הסבר

• עבור החוק $S=\varnothing$, קיימים שלושה ערכי צבעוניות: $[1,1,1]$, $[2,1,1]$, $[3,1,1]$;
• עבור החוק $S=\{1\}$, קיימים שני ערכי צבעוניות: $[1,1,1]$, $[2,1,1]$;
• עבור החוק $S=\{2\}$, קיימים שני ערכי צבעוניות: $[1,1,1]$, $[2,1,1]$;
• עבור החוק $S=\{1,2\}$, קיים ערך צבעוניות אחד: $[1,1,1]$.

לכן התשובה היא $3+2+2+1=8$.

קלט 2

0 6
0 1 0 3 1

פלט 2

279

דוגמה 3

ראו את rainbow/rainbow3.in ואת rainbow/rainbow3.ans בתיקיית המתחרים.

הדוגמה מקיימת את מגבלות בדיקות $3,4$.

דוגמה 4

ראו את rainbow/rainbow4.in ואת rainbow/rainbow4.ans בתיקיית המתחרים.

הדוגמה מקיימת את מגבלות בדיקות $5\sim7$.

דוגמה 5

ראו את rainbow/rainbow5.in ואת rainbow/rainbow5.ans בתיקיית המתחרים.

הדוגמה מקיימת את מגבלות בדיקות $8,9$.

דוגמה 6

ראו את rainbow/rainbow6.in ואת rainbow/rainbow6.ans בתיקיית המתחרים.

הדוגמה מקיימת את מגבלות בדיקות $10\sim12$.

מגבלות

בכל מקרי הבדיקה מתקיים:

• $1\le n\le200$;
• לכל $1\le i<n$ מתקיים $0\le f_i<i$.

תכונה מיוחדת A: לכל $1\le i<n$ מתקיים $f_i=i-1$.

תכונה מיוחדת B: לכל $0\le i<n$ קיימים לכל היותר שני ערכי $j$ המקיימים $f_j=i$.