Бір күні JOI-кун уақыт машинасына ие болды. Ол IX ғасырдағы Жапонияға баруды ұйғарды. Ол сол кездегі Жапониядағы ең атақты дін қызметкерлерінің бірі Кукайды кездестірді. Дін қызметкері жаттығудың жаңа тәсілін ойлап тапқысы келді.

Оның жаттығуы келесі түрде жүзеге асырылады:

• Кукай $N$ сөйлемнен тұратын сутраны оқиды. Бұл сөйлемдер реттелген, және ол оларды ретімен оқуы керек.
• Әр сөйлемде $1$ мен $N$ аралығындағы (шеткі мәндерді қоса алғанда) бір бүтін сан бар. Ешқандай екі түрлі сөйлемде бірдей сан болмайды.
• Ол $i$ ($1 \le i \le N$) бүтін саны бар сөйлемді бір күндегі теңдей бөлінген $N$ уақыт кезеңінің ішіндегі $i$-ші кезеңде оқуы керек. Әр сөйлемнің қысқа болғаны соншалық, оған бір кезеңде бір сөйлемді оқу әрқашан мүмкін болады.

Кукай бүкіл сутраны мүмкіндігінше тезірек оқып шыққысы келеді. Алайда, оны аяқтауға қанша күн кететіні сутрадағы сөйлемдердегі бүтін сандарға байланысты. Кукай JOI-куннан егер ол тиімді түрде оқыса, оқып бітіруге дәл $K$ күн кететіндей сөйлемдердегі бүтін сандардың орналасуының мүмкін тәсілдер санын есептеп беруді сұрады.

Тапсырма

Сөйлемдер саны $N$ және $K$ бүтін саны берілген. Егер Кукай тиімді түрде оқыса, оқып бітіруге дәл $K$ күн кететіндей сөйлемдердегі бүтін сандардың мүмкін орналасу тәсілдерінің санын $1\,000\,000\,007$ модулі бойынша есептеңіз.

Кіріс форматы

Стандартты кірістен келесі деректерді оқыңыз.

• Кірістің бірінші қатарында бір бос орынмен бөлінген $N$ және $K$ берілген.

Шығыс форматы

Егер Кукай тиімді түрде оқыса, оқып бітіруге дәл $K$ күн кететіндей сөйлемдердегі бүтін сандардың мүмкін орналасу тәсілдерінің санын $1\,000\,000\,007$ модулі бойынша шығарыңыз.

Шектеулер

Барлық кіріс деректері келесі шарттарды қанағаттандырады.

• $1 \le N \le 100\,000$.
• $1 \le K \le N$.

Ішкі есептер

Барлығы 4 ішкі есеп бар. Әрбір ішкі есептің ұпайы мен қосымша шектеулері келесідей:

Ішкі есеп 1 [4 ұпай]

• $N \le 10$.

Ішкі есеп 2 [20 ұпай]

• $N \le 300$.

Ішкі есеп 3 [25 ұпай]

• $N \le 3\,000$.

Ішкі есеп 4 [51 ұпай]

Қосымша шектеулер жоқ.

Мысалдар

Кіріс 1

3 2

Шығыс 1

4

Ескертпе

Оған оқып бітіруге 2 күн кететіндей сөйлемдердегі бүтін сандардың 4 мүмкін орналасу тәсілі бар.

• Бірінші сөйлемде 1, келесі сөйлемде 3 және соңғы сөйлемде 2 бар. Ол алғашқы екі сөйлемді (сәйкесінше 1 және 3 деп нөмірленген) бірінші күні, ал соңғы сөйлемді (2 деп нөмірленген) екінші күні оқиды.
• Бірінші сөйлемде 2, келесі сөйлемде 1 және соңғы сөйлемде 3 бар.
• Бірінші сөйлемде 2, келесі сөйлемде 3 және соңғы сөйлемде 1 бар.
• Бірінші сөйлемде 3, келесі сөйлемде 1 және соңғы сөйлемде 2 бар.

Кіріс 2

10 5

Шығыс 2

1310354