Masala #0907

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 44 %
4.2 (Baholar 4)
14

  

Chiroqlar

Sardor yashaydigan uyda ketma ket joylashgan nn ta chiroq bor. Chiroqlar 11 dan nn gacha raqamlangan. U barcha chiroqlarni yoqib chiqishni istaydi, dastlab bir nechta chiroqlar yoniq bo'lishi mumkin. 

Sardor bir harakatda yoniq chiroqning(chap yoki o'ng) qo'shni chiroqlaridan birini yoqishi mumkin bo'lsa, jami bo'lib barcha chiroqlarni yoqish usullari soni topish talab etiladi. 


Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida ikkita n(1n1000)n(1\leq n\leq 1000) va m(1mn)m(1\leq m\leq n) sonlari, mos ravishda uydagi chiroqlar soni va dastlabki yoniq chiroqlar soni.

Kiyingi satrda nn dan katta bo'lmagan mm xil natural sonlar - dastlab yoniq turgan chiroqlarning raqamlari. 


Chiquvchi ma'lumotlar:

Masalaning javobini 109+710^9 + 7 ga bo'lgandagi qoldiqni chop eting.


Misollar
# input.txt output.txt
1
2 1
1
1
2
4 2
2 4
2
Izoh:

Dastlab barcha chiroqlar yoniq holatda bo'lsa 11 xil usul deb tanlang.

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin