پس از فوت آقای عطایی بزرگ، تبارنامه خاندان عطایی به ارشیا رسید. این تبارنامه روی یک کاغذ با هزار سال قدمت نوشته شده است. ارشیا که از المپیاد کامپیوتری‌های سابق است، می‌خواهد نسخه الکترونیکی آن را بسازد.

ارشیا باید به هر راس از این درخت ریشه‌دار، یک شماره نسبت بدهد تا در ذخیره‌سازی کار راحت‌تری داشته باشد. او می‌داند که از قبل به هر فرد در تبارنامه یک شماره یکتا بین $1$ تا $n$ نسبت داده شده است، ولی این اطلاعات در اثر پوسیدگی کاغذ از بین رفته‌اند.

پدربزرگ ارشیا داده‌ی جالبی از شماره‌ی افراد می‌داند. خاندان عطایی یک فرد از خاندان را محترم می‌دانستند، اگر اختلاف شماره‌ی بیشینه و کمینه در میان او و فرزندانش و نوه‌هایش و … به اندازه یکی کمتر از تعدادشان بود. به بیانی دیگر، اگر $Ch_v$ را $v$ و تمام کسانی که $v$ پدربزرگشان است در نظر بگیریم، آنگاه $$\max_{u \in Ch_v} id_u - \min_{w \in Ch_v} id_w + 1 = \lvert Ch_v \rvert$$ که $id_v$ شماره منسوب به فرد $v$ است. پدربزرگ ارشیا تمامی افراد محترم را می‌شناسد و آن‌ها را به ارشیا می‌گوید تا کمکی به او کرده باشد.

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

در خط اول ورودی عدد صحیح $n$ تعداد افراد در تبارنامه می‌آید.

در خط بعدی $n-1$ عدد طبیعی $parent_2, parent_3, \ldots, parent_n$ به‌ترتیب می‌آیند. $parent_i$ پدر فرد $i$ است و فرد $1$ پدربزرگ خاندان عطایی است. دقت کنید که این شماره‌ها ربطی به شماره‌های تبارنامه ندارد.

در خط بعدی $n$ عدد صحیح $a_1, a_2, \ldots, a_n$ به‌ترتیب می‌آیند. اگر $a_i = 1$ فرد $i$ محترم است وگرنه $a_i = 0$ است و فرد $i$ به عنوان فردی محترم شناخته نمی‌شود.

در تنها خط خروجی یک عدد صحیح چاپ کنید که تعداد روش‌های شماره‌گذاری تبارنامه را نشان می‌دهد. دقت کنید کافیست که باقی‌مانده تقسیم آن بر $10^9 + 7$ را چاپ کنید.

• زیرمسئله اول (۶ نمره): $n \leq 10$
• زیرمسئله دوم (۵ نمره): تمام افراد محترم هستند.
• زیرمسئله سوم (۱۳ نمره): حداکثر ۱۰ فرد وجود دارد که محترم نیست.
• زیرمسئله چهارم (۲۱ نمره): $n \leq 500$
• زیرمسئله پنجم (۵۵ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \leq n \leq 5 \, 000$
• $1 \leq parent_i < i$
• $0 \leq a_i \leq 1$

• سوال قبل
• سوال بعد