Dag einn eignaðist JOI-kun tímavél. Hann ákvað að fara til Japans á 9. öld. Hann hitti Kukai, einn frægasta prest í Japan á þeim tíma. Presturinn vildi þróa nýja aðferð við þjálfun.

Þjálfun hans fer fram á eftirfarandi hátt:

• Kukai les sútruna sem hefur $N$ setningar. Þessar setningar eru í ákveðinni röð og hann verður að lesa þær í röð.
• Hver setning hefur eina heiltölu á milli $1$ og $N$, að báðum meðtöldum. Engar tvær ólíkar setningar hafa sömu töluna.
• Hann verður að lesa setninguna með heiltölunni $i$ ($1 \le i \le N$) á $i$-ta tímabilinu af þeim $N$ jafnskiptu tímabilum sem dagurinn skiptist í. Hver setning er svo stutt að það er alltaf mögulegt fyrir hann að lesa setningu á einu tímabili.

Kukai vill lesa alla sútruna eins hratt og mögulegt er. Hins vegar fer það eftir heiltölunum á setningunum í sútrunni hversu marga daga það tekur hann að klára. Kukai bað JOI-kun um að telja fjölda mögulegra leiða til að setja heiltölur á setningarnar þannig að það taki Kukai nákvæmlega $K$ daga að klára lesturinn, ef hann les á besta mögulega hátt.

Verkefni

Gefinn er fjöldi setninga $N$ og heiltala $K$. Reiknið fjölda mögulegra leiða til að setja heiltölur á setningarnar þannig að það taki Kukai nákvæmlega $K$ daga að klára lesturinn, ef hann les á besta mögulega hátt, modulo $1\,000\,000\,007$.

Inntak

Lesið eftirfarandi gögn úr staðalinntaki.

• Fyrsta línan í inntakinu inniheldur $N$ og $K$, aðskilin með einu bili.

Úttak

Prentið fjölda mögulegra leiða til að setja heiltölur á setningarnar þannig að það taki Kukai nákvæmlega $K$ daga að klára lesturinn, ef hann les á besta mögulega hátt, modulo $1\,000\,000\,007$.

Skorður

Öll inntaksgögn uppfylla eftirfarandi skilyrði.

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

Undirverkefni

Það eru 4 undirverkefni. Stigagjöf og viðbótarskorður hvers undirverkefnis eru sem hér segir:

Undirverkefni 1 [4 stig]

• $N \le 10$.

Undirverkefni 2 [20 stig]

• $N \le 300$.

Undirverkefni 3 [25 stig]

• $N \le 3\,000$.

Undirverkefni 4 [51 stig]

Engar frekari skorður eru til staðar.

Dæmi

Inntak 1

3 2

Úttak 1

4

Skýring

Það eru 4 mögulegar leiðir til að setja heiltölur á setningarnar þannig að það taki hann 2 daga að klára lesturinn.

• Fyrsta setningin hefur 1, næsta setning hefur 3 og síðasta setningin hefur 2. Hann les fyrstu tvær setningarnar (númeraðar 1 og 3 hvor um sig) á fyrsta degi, og síðustu setninguna (númeraða 2) á öðrum degi.
• Fyrsta setningin hefur 2, næsta setning hefur 1 og síðasta setningin hefur 3.
• Fyrsta setningin hefur 2, næsta setning hefur 3 og síðasta setningin hefur 1.
• Fyrsta setningin hefur 3, næsta setning hefur 1 og síðasta setningin hefur 2.

Inntak 2

10 5

Úttak 2

1310354