+ الزمن المحدد: 1 ثانية + حد الذاكرة: 256 ميجابايت ---------- بعد أكثر من عامين من الانتظار والبحث عن فريق، اكتشف أبو إسحاق أنه سيتم عقد مسابقة البرمجة بشكل فردي! لذلك، شعر بخيبة أمل كبيرة وأصبحت أفكاره ملخبطة! الآن، لاستعادتها إلى حالتها الطبيعية، انتقلت الكرة إلى ملعبك. سلسلة أفكار أبو إسحاق هي رسم Graph بسيط ومتصل يتكون من $n$ عقدة و $m$ حافة. يخطط لإعادة هيكلتها خلال $k$ مرحلة، حيث يتم إضافة حافة واحدة في كل مرحلة بحيث يبقى الـ Graph بسيطًا ويحتوي على دور واحد على الأقل بطول فردي. (الـ Graph البسيط هو رسم يحتوي على حواف تصل بين عقد مختلفة ولا يحتوي على حلقات أو حواف متعددة). ومع ذلك، بما أن صحته العقلية مهمة بالنسبة له، فإنه يطلب منك أن تخبره بعدد الطرق المختلفة لأداء هذا العمل قبل البدء فيه. نظرًا لأن عدد الحالات قد يكون كبيرًا جدًا، يرجى إخباره بباقی قسمته على $10^{9} + 7$ (يتم التمييز بين طريقتين لتنفيذ خطوات $k$ إذا كان هناك خطوة مثل $i$ لا يتساوى فيها الحافتان المضافتان في الطريقة الأولى مع الحافتين المضافتين في الطريقة الثانية.). **يرجى ملاحظة أن ترتيب إضافة الـ $k$ حواف له أهمية جداً.** # الإدخال في السطر الأول من المدخلات، يكون هناك ثلاثة أرقام على التوالي: $n$، $m$، و $k$. وفي $m$ سطر تالي، يأتي زوج من الأرقام $v$ و $u$، حيث يشير إلى وجود ربط بين العقدة $v$ والعقدة $u$. $$3 \le n \le 1\ 000$$ $$n-1 \le m < {n \choose 2}$$ $$1 \le v, u \le n$$ $$m + k \le {n \choose 2}$$ $$1 \le k$$ **نضمن أن الـ Graph المدخل هو Graph متصل وبسيط.** # الإخراج في الإخراج، يجب عليك طباعة باقي القسمة من عدد الأساليب المطلوبة مقسومًا على $10^{9} + 7$. # مثال ## نموذج إدخال 1 ``` 4 2 2 1 2 3 4 ``` ## نموذج إخراج 1 ``` 4 ``` ## نموذج إدخال 2 ``` 10 9 18 5 8 10 5 9 5 7 9 4 10 3 1 1 8 6 1 2 5 ``` ## نموذج إخراج 2 ``` 500910062 ```