+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- گرچه آقا فیروز در تپ‌نپ خیلی اذیت شد ولی توانست پول خوبی به دست آورد. او تصمیم گرفت با این پول یک بازی فکری برای بچه‌هایش بخرد تا هوش ریاضی آن‌ها را پرورش دهد. وقتی آقا فیروز بازی را به پسرش علی داد، او خیلی خوشحال شد و سریع شروع به بازی کرد. بازی از یک صفحه تشکیل شده بود که روی آن دو عدد $n$ و $m$ نوشته شده بود و در زیر آن $n$ نقطه کشیده شده بود که $m$ جفت از آن‌ها با پاره‌خط‌هایی به‌صورت خط‌چین به هم وصل شده بودند. علی باید طوری پاره‌خط‌ها را با رنگ‌های ۱ و ۲ و ۳ رنگ‌آمیزی می‌کرد که در انتها هر پاره‌خطی که رنگ ۱ دارد، حتما حداقل یک پاره‌خط مجاور با رنگ ۲ داشته باشد. دو پاره‌خط مجاور هستند اگر یک سر آن‌ها مشترک باشد. علی که از راحتی این بازی جا خورده بود، تصمیم گرفت تا هوش ریاضی خود را به پدرش ثابت کند و تعداد روش‌های رنگ‌آمیزی صفحه با شرایط را به دست آورد. او که در ابتدا متوجه سختی مسئله نبود، پس از مدتی فکر کردن و ناتوانی در حل آن خیلی ناراحت شد. حال برای این که علی ناراحت نشود شما تعداد روش‌‌های رنگ‌آمیزی را به دست آورید و به او بگویید. همچنین به‌دلیل اینکه ممکن است خروجی بزرگ باشد، جواب را به باقیمانده $10^9 + 7$ چاپ کنید. # ورودی در خط اول دو عدد $n$ و $m$ آمده است که به ترتیب تعداد نقاط و پاره‌خط‌ها را نشان می‌دهد. در $i$امین خط از $m$ خط بعدی دو عدد $v_i$ و $u_i$ آمده است که نشان‌دهنده‌ وجود پاره‌خطی بین دو نقطه با شماره $v_i$ و $u_i$ می‌باشد. تضمین می‌شود همواره $v_i$ و $u_i$ متفاوت هستند و بین هر جفتی حداکثر یک پاره‌خط‌ قرار دارد. $$1 \le n \le 18$$ $$1 \le m \le \frac{n \times (n - 1)}{2}$$ $$1 \le v_i, u_i \le n$$ # خروجی در تنها خط خروجی، تعداد روش‌های رنگ‌آمیزی پاره‌خط‌ها را به باقیمانده $10^9 + 7$ به دست آورید به‌طوری که شرایط بازی رعایت شود. # مثال ## ورودی نمونه ۱ ``` 4 2 1 2 3 4 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 3 3 1 2 2 3 3 1 ``` ## خروجی نمونه ۲ ``` 20 ``` <details class="blue"> <summary> راهنمایی ۱ </summary> تعریف می‌کنیم: $dp_{i, mask}$ تعداد حالات رنگ کردن پاره‌خط‌های ۱ تا $i$ به صورتی که راس‌هایی که در $mask$ هستند، حداقل یک پاره‌خط با رنگ ۲ به آن‌ها متصل باشد چقدر است و از روی این $dp$ جواب مساله را به دست می‌آوریم. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> برای بدست آوردن مقدار $dp_{i, mask}$ روی رنگ پاره‌خط $i$ ام حالت‌بندی می‌کنیم. اگر رنگ پاره‌خط $i$ بخواهد یک باشد، حتما باید یکی از دوسر پاره‌خط $i$ در $mask$ آمده باشد و رنگ کردن بقیه پاره‌خط‌ها $dp_{i-1, mask}$ حالت دارد. اگر رنگ پاره‌خط $i$ بخواهد سه باشد، رنگ کردن بقیه پاره‌خط‌ها $dp_{i-1, mask}$ حالت دارد. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> هم‌چنین اگر رنگ پاره‌خط $i$ بخواهد دو باشد روی $mask$ بدون پاره‌خط $i$ حالت‌بندی می‌کنیم. تعداد پاره‌خط‌هایی که تنها پاره‌خط مجاور آن‌ها با رنگ ۲، یال $i$ است را بدست میاوریم و $dp_{i, mask}$ را با توجه به این مقادیر حساب می‌کنیم. </details> <details class="blue"> <summary> راهنمایی ۴ </summary> حال از روی $dp$ گفته شده در بالا می‌توان جواب مساله را پیدا کرد. </details>

حل سؤال در بانک سؤالات