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

پشمک و پارمیدا در پوستون زندگی می‌کنند. امسال در جشن سال نو، پشمک یک گردنبند به پارمیدا هدیه داده است. یک گردنبند در پوستون تعدادی مهره دارد که روی هر یک از مهره‌های آن‌ یک رقم بین $0$ تا $9$ نوشته شده است. بنابراین هر گردنبند، متناظر با یک عدد ‌صحیح نامنفی است که مهره‌های آن، از چپ به راست، رقم‌های آن عدد را، از پر ارزش‌ترین به کم‌ارزش‌ترین، نشان می‌دهند. دقت کنید که در چپ ترین مهره‌ی یک گردنبند تنها در حالتی امکان دارد رقم $0$ نوشته شده باشد که عدد متناظر با گردنبند، صفر باشد (یعنی گردنبند تنها یک مهره‌ با رقم $0$ داشته باشد) زیرا پر ارزش‌ترین رقم یک عدد بزرگتر از صفر، نمی‌تواند $0$ باشد.

قیمت یک گردنبند که مهره‌های آن، به ترتیب از چپ به راست، $a_1, a_2, \ldots, a_n$ هستند، برابر تعداد نابجایی‌های دنباله‌ی مهره‌های آن است. به عبارت دیگر قیمت یک گردنبند، تعداد جفت‌های $(i, j)$ است که:

• $i < j$
• $a_i > a_j$

دقت کنید در صورتی که دنباله‌ی مهره‌های یک گردنبند صعودی باشد، قیمت آن برابر با صفر خواهد بود.

هم‌چنین هر چه عدد متناظر با یک گردنبند کوچکتر باشد، آن گردنبند جذاب‌تر خواهد بود. برای مثال، جذاب‌ترین گردنبند گردنبندی است که عدد متناظر با آن برابر با صفر باشد.

به ازای هر عدد صحیح نامنفی، دقیقاً یک گردنبند در پوستون وجود دارد که متناظر با این عدد است. پارمیدا، از روی کنجکاوی می‌خواهد تعداد گردنبندهای جذاب‌تر و با قیمت کمتر از گردنبدی که هدیه گرفته است را بشمارد. برنامه‌ای بنویسید که این عدد را محاسبه کند.

ورودی🔗

در خط اول ورودی $n$، عدد متناظر با گردنبندی که پشمک به پارمیدا هدیه داده است، آمده است. $1 \le n \le 10^{18}$

خروجی🔗

در تنها خط خروجی، تعداد گردنبندهای جذاب‌تر و با قیمت کمتر از گردنبند پارمیدا را چاپ کنید.

زیرمسئله‌ها🔗

مثال🔗

ورودی نمونه ۱🔗

123

خروجی نمونه ۱🔗

0

ورودی نمونه ۲🔗

1991

خروجی نمونه ۲🔗

999

ورودی نمونه ۳🔗

100000

خروجی نمونه ۳🔗

50248

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

یک گراف ساده‌ی همبند $n$ راسی به شما داده است. در ابتدا رنگ تمامی راس‌ها به جز دو راس $r$ و $b$، سفید است. راس $r$ قرمز رنگ است و یک مهره‌ی قرمز نیز روی آن وجود دارد. راس $b$ سیاه رنگ است و یک مهره‌ی سیاه روی آن وجود دارد.

در هر ثانیه به صورت تصادفی یکی از دو رنگ سیاه و قرمز انتخاب می‌شود و به ازای هر مهره از رنگ انتخاب شده، که برای مثال در راس $v$ قرار دارد، در تمامی راس‌های همسایه راس $v$ در گراف یک مهره‌ی جدید از همان رنگ قرار داده می‌شود. اگر راسی که مهره‌ی جدید در آن قرار می‌گیرد سفید باشد، رنگ راس به رنگ آن مهره‌ در خواهد آمد و در غیراین‌صورت رنگ راس تغییر نخواهد کرد.

راس‌های گراف در انتهای این عملیات، یعنی زمانی که تمامی راس‌ها رنگ شده‌اند، چند رنگ‌آمیزی متفاوت می‌توانند داشته باشند؟ دو رنگ ‌آمیزی متفاوت اند اگر رنگ یک راس در آن دو رنگ‌آمیزی متفاوت باشد.

ورودی🔗

در خط اول ورودی چهار عدد طبیعی $n$ و $m$ و $r$ و $b$، به ترتیب تعداد راس‌های گراف، تعداد یال‌های گراف، شماره‌ی راس $r$ و شماره‌ی راس $b$، آمده است. در هر یک از $m$ خط بعدی دو عدد طبیعی $v_i$ و $u_i$ آمده‌است که نشان‌دهنده‌ی وجود یک یال بین دو راس $v_i$ و $u_i$ در گراف است. گراف داده شده ساده و همبند است. $2 \le n \le 100\ 000$ $1 \le m \le min(\binom{n}{2}, 200\ 000)$ $1 \le r, b \le n$ $r \ne b$ $1 \le v_i, u_i \le n$

خروجی🔗

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

زیرمسئله‌ها🔗

مثال🔗

ورودی نمونه ۱🔗

4 3 2 3
1 2
2 3
3 4

خروجی نمونه ۱🔗

3

ورودی نمونه ۲🔗

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

خروجی نمونه ۲🔗

4

ورودی نمونه ۳🔗

8 9 1 2
1 3
3 2
1 4
4 5
5 2
1 6
6 7
7 8
8 2

خروجی نمونه ۳🔗

8

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

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

امین برای جابه‌جایی بین میدان‌ها در شهر می‌تواند از اوبر یا اسنپ تاکسی بگیرد! هر کدام از این دو شرکت مجموعه‌ای از خیابان‌های شهر را تحت پوشش قرار داده است، به طوری که با خیابان‌های تحت پوشش هر کدام از شرکت‌ها به تنهایی، می‌توان با یک مسیر یکتا از هر میدانی به هر میدان دیگر رفت. هم‌چنین، هیچ خیابانی وجود ندارد که تحت پوشش هر دو شرکت اوبر و اسنپ باشد.

امین می‌خواهد بین میدان‌های شهر دور دور کند. او عملیات دور دور را به این شکل انجام می‌دهد که از یک میدان دلخواه شروع می‌کند، از هیچ خیابانی بیش از یک بار عبور نمی‌کند و در نهایت به میدان نخست بر می‌گردد. او در هر حرکت یک بار از یکی از دو شرکت تاکسی می‌گیرد و با این کار از یک سر یک خیابان که تحت پوشش آن شرکت است به سر دیگر آن خیابان می‌رود.

به دلیل این که هزینه‌ی استفاده از تاکسی‌های اوبر بسیار زیاد است، امین حداکثر دوبار می‌تواند از آن‌ها استفاده کند، اما به هر تعداد دلخواهی می‌تواند از تاکسی‌های اسنپ استفاده کند. از طرفی تاکسی‌های اوبر به مراتب لوکس‌تر از تاکسی‌های اسنپ هستند و در نتیجه در نظر دارد که حتماً از دو مرتبه‌ای که می‌تواند هزینه‌ی تاکسی‌های اوبر را پرداخت کند استفاده کند. پس یک دور دور از نظر امین به صرفه است اگر و تنها اگر در طول آن دقیقاً دوبار از تاکسی‌های اوبر استفاده شود.

امین دو دور دور را در صورتی متفاوت در نظر می‌گیرد که در یکی از آن‌ها از خیابانی عبور کنیم که در دور دور دیگر از آن عبور نخواهیم کرد. آیا می‌توانید با گرفتن مسیرهای تحت پوشش اوبر و مسیرهای تحت پوشش اسنپ، تعداد دور دورهای مختلف که امین می‌تواند انجام دهد را بشمارید؟

ورودی🔗

در خط اول ورودی عدد $n$، تعداد میدان‌های پوستون، آمده است. در $n-1$ خط بعدی، در هر خط دو عدد طبیعی $v_{s,i}$ و $u_{s,i}$ آمده است که نشان‌ می‌دهد خیابان متصل کننده‌ی آن دو میدان تحت پوشش اسنپ است. در $n-1$ خط بعدی، در هر خط دو عدد طبیعی $v_{u,i}$ و $u_{u,i}$ آمده است که نشان‌ می‌دهد خیابان متصل کننده‌ی آن دو میدان تحت پوشش اوبر است. بین هر دو میدان حداکثر یک خیابان وجود دارد. با تاکسی‌های تحت پوشش هر شرکت می‌توان از هر میدان به هر میدان دیگر رسید.

$4 \le n \le 100\ 000$ $1 \le v_{s,i}, u_{s,i} \le n$ $1 \le v_{u,i}, u_{u,i} \le n$

خروجی🔗

در تنها خط خروجی، تعداد ‌دور دورهای به صرفه در پوستون را چاپ کنید.

زیرمسئله‌ها🔗

مثال🔗

ورودی نمونه ۱🔗

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

خروجی نمونه ۱🔗

3

ورودی نمونه ۲🔗

7 
1 2
1 3
2 4
2 5
3 6    
3 7
1 4
4 5
1 7
7 6
6 2
2 3

خروجی نمونه ۲🔗

12