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

بعد از یک کلاس ریاضیات سخت، حنا برای تفریح به همراه بنا به جنگل رفته است. حنا و بنا هر کدام یک درخت (گراف بدون دور و همبند) ریشه‌دار $n$ راسی انتخاب کرده‌اند. آن‌ها به یک دنباله از اعداد مانند $V_1, V_2, ..., V_K$ علاقه دارند اگر هر دو شرط زیر برقرار باشد:

• در درخت حنا، به ازای هر $1 \leq i < K$ راس $V_i$ جد راس $V_{i+1}$ است.
• در درخت بنا، به ازای هر $1 \leq i < K$ راس $V_{i+1}$ جد راس $V_i$ است.

آن‌ها عاشق یک دنباله هستند اگر هر دو شرط زیر برقرار باشد:

• به این دنباله علاقه داشته باشند.
• هیچ دنباله‌ای با طول بیشتر از این دنباله وجود نداشته باشد که به آن علاقه داشته باشند.

در یک درخت ریشه‌دار، به راس $v$ جد راس $u$ می‌گوییم اگر یکی از دو شرط زیر برقرار باشد:

• راس $v$ پدر راس $u$ باشد.
• راس $v$ جد پدر راس $u$ باشد.

طول بزرگ‌ترین دنباله‌ای که حنا و بنا به آن علاقه دارند، و تعداد دنباله‌هایی که آن‌ها عاشق آن هستند، چقدر است؟

ورودی

در سطر اول ورودی، عدد $n$ آمده‌است.

در $n - 1$ سطر بعدی یال‌های درخت حنا آمده‌است. در $i$ امین سطر $v_i$ و $u_i$ دو سر یال $i$ ام در درخت حنا آمده‌است. ریشه درخت حنا راس شماره $1$ است.

در $n - 1$ سطر بعدی یال‌های درخت بنا آمده‌است. در $i$ امین سطر $v_i$ و $u_i$ دو سر یال $i$ ام در درخت بنا آمده‌است. ریشه درخت بنا راس شماره $n$ است.

$$1 \leq n \leq 200 , 000$$ $$1 \leq v_i, u_i \leq n$$

خروجی

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

مثال

ورودی نمونه ۱

5
4 2
3 1
5 4
2 1
4 5
1 5
3 4
2 5

خروجی نمونه ۱

2 3