+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + روز ۲ دوره ۳۰ ---------- مهدی به پدرام یک گراف ساده و همبند $n$ راسی و $m$ یالی کادو داده است.البته این گراف یک گراف عادی نیست. هر راس در حداکثر یک دور ظاهر می‌شود. پدرام برای قدر‌دانی از هدیه‌ی مهدی، تصمیم گرفته‌است که تعداد زیردرخت‌های القایی گرافی که مهدی به او داده‌است را حساب کند. حالا شما به پدرام کمک کنید و جواب را برای او به دست آورید. پدرام برای کمک به شما، توضیحی در مورد زیر گراف القایی به شما داده است: زیرگراف القایی یک گراف، مجموعه‌ای از راس های آن گراف و همه‌ی یال‌هایی است که دو سرشان از میان راس‌های انتخاب شده باشد. زیردرخت القایی ، یک زیرگراف القایی است، که راس‌ها و یال‌هایش تشکیل یک درخت بدهد. # ورودی در سطر اول ورودی عدد $n$ و $m$ آمده است . در هر یک از $m$ خط بعدی دو عدد که نمایانگر دو سر یک یال‌اند، آمده است. $$1 \le n \le 10^5$$ # خروجی در تنها سطر خروجی، باقی مانده‌ی عددی که پدرام می‌خواهد را به $10^9+7$ چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۸ | $n \le 20$ | | ۲ | ۱۲ | $m = n - 1$ یا به عبارتی گراف ورودی درخت است. | | ۳ | ۳۰ | $n \le 5000$ | | ۴ | ۵۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 5 1 2 2 3 3 4 4 1 4 5 ``` ## خروجی نمونه ۱ ``` 19 ``` ## ورودی نمونه ۲ ``` 5 4 1 2 1 3 2 4 2 5 ``` ## خروجی نمونه ۲ ``` 17 ``` ## ورودی نمونه ۳ ``` 8 9 1 2 2 3 3 1 3 4 4 5 5 6 6 7 7 4 7 8 ``` ## خروجی نمونه ۳ ``` 52 ```

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