كان أحمقان يسيران في الشارع...
الأحمق الأول: لقد فكرت في مسألة رائعة جدًا. لديك رسم بياني موجّه خالٍ من الدورات، أو DAG... وتريد إسناد وزن $0$ أو $1$ إلى كل حافة، بحيث لا يعتمد وزن المسار بين أي رأسين على اختيار المسار...
الأحمق الثاني: همم... لكن ماذا لو لم يوجد مسار بين رأسين ما؟
الأحمق الأول: حسنًا، نعم، عندما يوجد أكثر من مسار، تكون أوزانها كلها متساوية. على أي حال، المطلوب هو عدد طرق إسناد الأوزان هذه.
الأحمق الثاني: نعم، مسألة جيدة...
لحسن الحظ، التقيا حينها بصديقهما غير الأحمق.
غير الأحمق: أنتما بالتأكيد لا تعرفان كيف تحلانها، أي إنكما تتخبطان. لكنني أعرف كيف أحل مسألة أبسط قليلًا. لا يمكنني أن أشترط ألا تعتمد المسافة بين الرؤوس على اختيار المسار، لكن يمكنني أن أشترط ألا تعتمد المسافة بترديد $2$ عليه...
الأحمقان الأول والثاني: orz
والآن، بصياغة رسمية، يُعطى رسم بياني موجّه يحتوي على $N$ رأسًا و$M$ حافة. الرؤوس مرقمة من $1$ إلى $N$، ولكل حافة موجّهة $(u,v)$ يتحقق $u<v$. نسمّي إسناد قيمة $0$ أو $1$ إلى كل حافة تلوينًا للحواف. نرمز إلى قيمة الحافة $(u,v)$ بالرمز $w(u,v)$.
المسار بين الرأسين $u$ و$v$ هو أي متتالية رؤوس $(a_1,\ldots,a_k)$ تحقق $a_1=u$ و$a_k=v$. كذلك، لكل $i$ بين $1$ و$k-1$، يجب أن توجد الحافة $(a_i,a_{i+1})$. وزن المسار هو مجموع أوزان جميع حوافه، أي $w(a_1,a_2)+\cdots+w(a_{k-1},a_k)$.
يكون التلوين $w$ جيدًا إذا كان، لكل زوج من الرؤوس $(u,v)$ ولكل زوج من المسارات بينهما، لوزني هذين المسارين الباقي نفسه عند القسمة على $2$.
بما أن عدد التلوينات الجيدة قد يكون كبيرًا، اطبع باقي قسمته على $10^9+7$.
الإدخال
يحتوي السطر الأول على العددين الطبيعيين $N$ و$M$.
تحتوي الأسطر $M$ التالية على أزواج مختلفة من العددين $u$ و$v$، حيث $1\le u<v\le N$، تمثل حواف الرسم البياني.
الإخراج
اطبع في سطر واحد باقي قسمة عدد التلوينات الجيدة على $10^9+7$.
المهام الفرعية
في جميع المهام الفرعية يتحقق $1\le N\le400$ و$0\le M\le400$.
| المهمة الفرعية | النقاط | القيود |
|---|---|---|
| 1 | 21 | $N\le6$ |
| 2 | 20 | $N\le13$ |
| 3 | 37 | $N,M\le50$ |
| 4 | 22 | لا توجد قيود إضافية. |
أمثلة
الإدخال 1
4 4 1 2 2 3 3 4 1 4
الإخراج 1
8
الإدخال 2
4 4 1 3 1 4 2 3 2 4
الإخراج 2
16
ملاحظة
توضيح المثال الأول:
يجب أن يكون للمسارين $1\to2\to3\to4$ و$1\to4$ الوزنان نفسيهما بترديد $2$. إذا أسندنا الوزن $0$ إلى الحافة $(1,4)$، فيجب أن يكون عدد الحواف المتبقية ذات الوزن $1$ زوجيًا، مما يعطي $4$ إمكانيات. أما إذا أسندنا الوزن $1$ إلى الحافة $(1,4)$، فيجب أن يكون عدد الحواف المتبقية ذات الوزن $1$ فرديًا، مما يعطي أيضًا $4$ إمكانيات.