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

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

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

در خط اول ورودی چهار عدد طبیعی $n$ و $m$ و $r$ و $b$، به ترتیب تعداد راس‌های گراف، تعداد یال‌های گراف، شماره‌ی راس $r$ و شماره‌ی راس $b$، آمده است.

در هر یک از $m$ خط بعدی دو عدد طبیعی $v_i$ و $u_i$ آمده‌است که نشان‌دهنده‌ی وجود یک یال بین دو راس $v_i$ و $u_i$ در گراف است.

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

• زیرمسئله اول (۱۷ نمره): $n \le 20$
• زیرمسئله دوم (۲۶ نمره): $n \le 1000$
• زیرمسئله سوم (۵۷ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $2 \le n \le 10^5$
• $1 \le m \le min(\binom{n}{2}, 2 \times 10^5)$
• $1 \le r, b \le n$
• $r \ne b$
• $1 \le v_i, u_i \le n$
• گراف داده شده ساده و همبند است.

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