Masala #0907

Xotira 16 MB Vaqt 1000 ms
14

Chiroqlar

Sardor yashaydigan uyda ketma ket joylashgan \(n\) ta chiroq bor. Chiroqlar \(1\) dan \(n\) 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(1\leq n\leq 1000)\) va \(m(1\leq m\leq n)\) sonlari, mos ravishda uydagi chiroqlar soni va dastlabki yoniq chiroqlar soni.

Kiyingi satrda \(n\) dan katta bo'lmagan \(m\) xil natural sonlar - dastlab yoniq turgan chiroqlarning raqamlari. 


Chiquvchi ma'lumotlar:

Masalaning javobini \(10^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 \(1\) xil usul deb tanlang.