اختلاف طبقاتی (Class Conflict)

رابین هود بدترین پدیده اجتماعی را اختلاف طبقاتی می‌داند و تمام زندگانیش را وقف مبارزه با اختلاف طبقاتی کرده است. اما سالیان سال تقلای فراوان و بی‌نتیجه او را به پوچ‌گرایی رسانیده است. رابین هود تنها راه از بین بردن اختلاف طبقاتی را از بین بردن طبقات می‌پندارد.

در شهر ناتینگهام $n$ نفر زندگی می‌کنند. در روز یکشنبه همه مردم شهر برای پرداخت مالیات رو‌به‌روی خانه‌ی داروغه و در خیابان اصلی در یک صف ایستاده‌اند. رابین هود در این روز خفت‌بار از دور به تماشای این صحنه می‌پردازد. او که تازگی در رویا و خیال‌پردازی به سر می‌برد، یک سناریوی ذهنی را متصور می‌شود.

او طبقه اجتماعی شخص $i$ام در صف را عدد طبیعی $a_i$ تخمین می‌زند. از آنجا که می‌داند برای از بین بردن اختلاف طبقاتی باید تمام طبقات را از بین ببرد، یک طبقه جدید با نام پوچی و با عدد $0$ معرفی می‌کند. در این سناریو ذهنی، یک شخص خیالی با طبقه اجتماعی $0$ به اول صف و یکی دیگر به آخر صف اضافه می‌کند. سپس نبرد اختلافات آغاز خواهد شد.

در هر مرحله در طول نبرد، او دو نفر متوالی در صف را انتخاب می‌کند و آن‌ها را به جدال می‌فرستد. فقط یکی از این دو نفر می‌تواند از جدال زنده بیرون بیاید. از آن‌جا که رابین هود از ثروتمندان نفرت دارد، می‌خواهد در هر جدال فرد با طبقه اجتماعی پایین‌تر پیروز شود. برای پیروزی این فرد، رابین هود باید به اندازه‌ی اختلاف طبقاتی آن‌دو به او یاری کند. به عبارتی دیگر در هر جدال شخص با طبقه اجتماعی بالاتر از صف حذف شده و شخص با طبقه اجتماعی پایین‌تر به سر جای خود در صف برمی‌گردد. این جدال به اندازه‌ی اختلاف طبقاتی این دو نفر از رابین هود یاری می‌طلبد. نبرد زمانی به پایان می‌رسد که تنها افراد با طبقه اجتماعی $0$ باقی‌مانده باشند. در این لحظه ما به پوچی رسیده‌ایم.

با وجود این که این یک سناریو ذهنی است، یاری کردن انرژی زیادی از رابین می‌گیرد. به همین خاطر او می‌خواهد جدال‌ها را طوری برنامه‌ریزی کند تا با کمترین هزینه به پوچی برسد. رابین که بعد از فعالیت اجتماعی، برنامه‌ریزی را سرلوحه‌ی کار خود قرار داده‌است، می‌خواهد بداند چند روش مختلف برای رسیدن به هدفش با کمترین هزینه ممکن وجود دارد. دو روش با هم متفاوتند اگر و تنها اگر در یکی از مراحل این دو روش جفت متفاوتی با هم به جدال رفته باشند.

در خط اول ورودی عدد $n$ و پس از آن عدد $c$ آمده است. درباره‌ی عدد $c$ در بخش خروجی بخوانید. در خط دوم $n$ عدد آمده‌است که به ترتیب $a_1, a_2, \cdots, a_n$ را نشان می‌دهند.

در خط اول خط خروجی، کمترین میزان یاری‌رسانی از طرف رابین هود تا به پوچی برسیم را چاپ کنید.

در خط دوم در صورتی که:

• $c = 0$: باید عدد $0$ را چاپ کنید.
• $c = 1$: تعداد روش‌های مختلف رسیدن به هدف را به پیمانه $10^9+7$ چاپ کنید.

• زیرمسئله اول (۶ نمره): $n \le 20$.
• زیرمسئله دوم (۵ نمره): آرایه $a$ به شکل یک قله است.
• زیرمسئله سوم (۱۳ نمره): آرایه $a$ به شکل یک دره است.
• زیرمسئله چهارم (۳۶ نمره): $c = 0$.
• زیرمسئله پنجم (۴۰ نمره): بدون محدودیت اضافی.

• $1 \leq n \leq 2 \times 10^5$
• $1 \leq a_i \leq 10^9$
• $c \in \lbrace 0, 1 \rbrace $
• همه اعضای آرایه $a$ متمایزند.

4 1
1 6 3 9

12
4

4 0
1 6 3 9

12
0

10 3 10
1 0 2 2 4 7 1 3 1 1
1 8 9 2
1 3 8 3
2 9 7
1 6 8 6
2 6 4
1 4 6 7
1 1 10 3
2 1 2
2 10 1
1 1 4 3

0
248
0
4
736
2

$ \lbrace 0, 1, 6, \underline{3, 9}, 0 \rbrace \rightarrow \lbrace 0, 1, \underline{6, 3}, 0 \rbrace \rightarrow \lbrace 0, \underline{1, 3}, 0 \rbrace \rightarrow \lbrace \underline{0, 1}, 0 \rbrace \rightarrow \lbrace 0, 0 \rbrace $

$ \lbrace 0, 1, 6, \underline{3, 9}, 0 \rbrace \rightarrow \lbrace 0, 1, \underline{6, 3}, 0 \rbrace \rightarrow \lbrace 0, \underline{1, 3}, 0 \rbrace \rightarrow \lbrace 0, \underline{1, 0} \rbrace \rightarrow \lbrace 0, 0 \rbrace $

$ \lbrace 0, 1, \underline{6, 3}, 9, 0 \rbrace \rightarrow \lbrace 0, 1, \underline{3, 9}, 0 \rbrace \rightarrow \lbrace 0, \underline{1, 3}, 0 \rbrace \rightarrow \lbrace \underline{0, 1}, 0 \rbrace \rightarrow \lbrace 0, 0 \rbrace $

$ \lbrace 0, 1, \underline{6, 3}, 9, 0 \rbrace \rightarrow \lbrace 0, 1, \underline{3, 9}, 0 \rbrace \rightarrow \lbrace 0, \underline{1, 3}, 0 \rbrace \rightarrow \lbrace 0, \underline{1, 0} \rbrace \rightarrow \lbrace 0, 0 \rbrace $

در بالا تمام $4$ حالت مختلف رسیدن به پوچی با کمترین میزان یاری نشان داده شده است. در هر مرحله دو نفری که زیرشان خط کشیده شده است به جدال می‌روند. در $2$ حالت اول میزان یاری‌رسانی به ترتیب $6$، $3$، $2$ و $1$ و در $2$ حالت بعدی میزان یاری‌رسانی به ترتیب $3$، $6$، $2$ و $1$ است.