محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۵۱۲ مگابایت

در یک شرکت برنامه‌نویسی، $n$ برنامه‌نویس مشغول به کار هستند. این برنامه‌نویس‌ها با اعداد ۱ تا $n$ شماره‌گذاری می‌شوند. سیستم مدیریتی این شرکت به صورت یک درخت است. یعنی هر برنامه‌نویس به جز برنامه‌نویس شماره‌ی ۱، یک مدیر دارد. مدیر برنامه‌نویس $i$ را با $p_i$ نشان می‌دهیم. در واقع ساختار این شرکت به صورت یک درخت ریشه‌دار است.

عید نوروز نزدیک است و این برنامه‌نویس‌ها می‌خواهند از شرکت خارج شوند و برای سفر به شهر کدکاپ بروند. زمانی برنامه‌نویس شماره‌ی $i$ می‌تواند از شرکت خارج شود که $p_i$ هم از سازمان خارج شده باشد.

برای هر $k$ از ۱ تا $n$ حساب کنید چند زیرمجموعه $k$ عضوی از برنامه‌نویس‌ها می‌توانند از شرکت خارج شوند. چون ممکن است پاسخ خیلی بزرگ باشد، باقی‌مانده‌ی آن را بر $10^9 + 7$ چاپ کنید.

ورودی

در سطر اول ورودی، عدد صحیح و مثبت $n$ آمده که تعداد برنامه‌نویس‌های شرکت را نشان می‌دهد. $2 \leq n \leq 10 , 000$

در سطر دوم ورودی، $n - 1$ عدد صحیح $p_2, p_3, \dots, p_n,$ می‌آید. $1 \leq p_i \lt i$

خروجی

خروجی $n$ سطر دارد و در سطر $k$ ام تعداد حالت‌هایی که $k$ نفر شرکت را ترک کنند محاسبه کنید.

مثال‌ها

ورودی نمونه ۱

3
1 1

خروجی نمونه ۱

1 2 1

توضیح نمونه ۱

توضیح تصویر

برای حالت $k = 1$ فقط باید یک برنامه‌نویس شرکت را ترک کند و آن فقط $1$ است. (۱ حالت)
برای حالت $k = 2$ فقط باید دو برنامه‌نویس شرکت را ترک کنند و آن‌ها می‌توانند $1, 2$ یا $1, 3$ باشند. (۲ حالت)
برای حالت $k = 3$ فقط باید سه برنامه‌نویس شرکت را ترک کنند و آن‌ها می‌توانند $1, 2, 3$ هستند. (۱ حالت)

ورودی نمونه ۲

5
1 1 2 2

خروجی نمونه ۲

1 2 3 3 1

توضیح نمونه ۲

توضیح تصویر

مشابه نمونه‌ی قبل مجموعه افرادی که می‌توانند خارج شوند عبارت است از:

$k = 1 \to {1}$ $k = 2 \to {1, 2}, {1, 3}$ $k = 3 \to {1, 2, 3}, {1, 2, 4}, {1, 2, 5}$ $k = 4 \to {1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}$ $k = 5 \to {1, 2, 3, 4, 5}$

ارسال پاسخ برای این سؤال