+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مربّاها تازه با گراف آشنا شده‌اند و از قضا، خیلی هم از گراف خوششان آمده. به خاطر همین مربّاها تصمیم گرفتند یک جشن برای گراف‌ها برگزار کنند. مربّاها که آشنایی چندانی با گراف نداشتند، جشن را با یک گراف کوچک و جمع و جور شروع کردند. در واقع مربّاها جشن‌شان را با یک گراف دو راسی برچسب‌دار ساده شروع کردند که تنها یال آن راس شماره‌ی یک را به راس شماره‌ی دو وصل می‌کرد. قرار بود که در روز جشن هر کدام از مربّاها به همراه یک راس برچسب‌دار به جشن بیاید و یکی از یال‌های گراف را که تا حالا نوچ نشده، انتخاب کند و آن را نوچ کند، پس از آن هم راس برچسب‌دار خود را با استفاده از دو یال تمیز به دو سر یالی که نوچ کرده، وصل کند. اما شب قبل از جشن یکی از عسل‌ها که چشم دیدن جشن مربّاها را نداشت، برچسب‌هایی را که مربّاها در اختیار داشتند دزدید. صبح که مربّاها از خواب بیدار شدند دیدند که هیچ‌کدام از راس‌هایشان برچسب ندارد. همه‌ی مربّاها از فرط ناراحتی شربت گریه می‌کردند. بزرگ مربّاها که این وضع را دید، رفت و از داخل گاوصندوقش دو برچسب پیدا کرد و این دو برچسب را به دو راس گراف اولیه چسباند. مربّاها هم از این که این اتفاق افتاد کلی خوشحال شدند. بعد از این که همه‌ی مربّاها راس بدون برچسب خودشان را به گراف چسباندند، بزرگ مربّاها آن‌ها را دور هم جمع کرد و معمایی را برای آن‌ها مطرح کرد. بزرگ مربّاها ابتدا معنی بیشینه‌ شار (max flow) را در گراف برای مربّاها توضیح داد و سپس از آن‌ها خواست که بگویند در تمام حالات برگزاری جشن توسط مربّاها چند گراف با بیشینه شار حداقل $m$ از راس ۱ به راس ۲ تولید می‌شد. دو حالت برگزاری جشن متفاوتند اگر و فقط اگر گراف ساخته شده در پایان این دو جشن متفاوت باشد، در واقع ترتیب انتخاب یال‌ها مهم نیست. دقت کنید، راس‌های افزوده شده برچسب ندارند (ولی راس ۱ و ۲ دارند). مربّاها که تازه با گراف آشنا شده بودند نتوانستند که این معما را حل کنند، به همین دلیل پیش شما آمدند تا جواب این معما را به آن‌ها بگویید و مربّاها شرمنده‌ی بزرگشان نشوند. البته آن‌ها متوجه این موضوع هستند که برای شما کار با اعداد خیلی بزرگ سخت است، به همین دلیل باقیمانده‌ی پاسخ معما را بر $10^9 + 7$ هم بگویید، مربّاها از شما متشکر خواهند شد. پی‌نوشت: می‌توانید از [اینجا](https://fa.wikipedia.org/wiki/%D9%85%D8%B3%D8%A6%D9%84%D9%87_%D8%A8%DB%8C%D8%B4%DB%8C%D9%86%D9%87_%D8%AC%D8%B1%DB%8C%D8%A7%D9%86#%D8%AA%D8%B9%D8%B1%DB%8C%D9%81) اطلاعات بیش‌تری درباره‌ی بیشینه شار به دست بیاورید. # ورودی در تنها خط ورودی، $n$ و $m$ می آیند که به ترتیب نشان دهنده تعداد مربّا و حداقل میزان بیشینه شار می باشند. $$1 \leq n, m \leq 10\ 000$$ # خروجی در تنها خط خروجی باقیمانده‌ی پاسخ معما بر $10^9 + 7$ را چاپ کنید. # مثال ### ورودی نمونه ۱ ``` 2 2 ``` ### خروجی نمونه ۱ ``` 2 ``` مربّای اول مجبور است تنها یال گراف را انتخاب کند. و نفر دوم هر یک از دو یال جدید را می‌تواند انتخاب کند. در هر دوی این حالات بیشینه شار برابر ۲ است.

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