Eräänä päivänä JOI-kun sai aikakoneen. Hän päätti matkustaa 800-luvun Japaniin. Hän tapasi Kukain, yhden sen ajan kuuluisimmista papeista Japanissa. Pappi halusi kehittää uuden harjoittelutavan.

Hänen harjoittelunsa tapahtuu seuraavalla tavalla:

• Kukai lukee suutran, jossa on $N$ lausetta. Nämä lauseet ovat järjestyksessä, ja hänen on luettava ne järjestyksessä.
• Jokaisella lauseella on yksi kokonaisluku väliltä $1$ ja $N$, rajat mukaan lukien. Millään kahdella eri lauseella ei ole samaa lukua.
• Hänen on luettava kokonaisluvulla $i$ ($1 \le i \le N$) merkitty lause $i$-nnessä jaksossa päivän $N$ yhtä suureen osaan jaetusta aikajaksosta. Jokainen lause on niin lyhyt, että hänen on aina mahdollista lukea lause yhden jakson aikana.

Kukai haluaa lukea koko suutran mahdollisimman nopeasti. Kuitenkin se, kuinka monta päivää häneltä kuluu lukemisen loppuun saattamiseen, riippuu suutran lauseissa olevista kokonaisluvuista. Kukai pyysi JOI-kunia laskemaan, kuinka monella mahdollisella tavalla kokonaisluvut voidaan asettaa lauseille niin, että Kukailta kuluu täsmälleen $K$ päivää lukemisen loppuun saattamiseen, jos hän lukee optimaalisesti.

Tehtävä

Kun annetaan lauseiden lukumäärä $N$ ja kokonaisluku $K$, laske sellaisten mahdollisten tapojen lukumäärä asettaa kokonaisluvut lauseille, joilla Kukailta kuluu täsmälleen $K$ päivää lukemisen loppuun saattamiseen hänen lukiessaan optimaalisesti, modulo $1\,000\,000\,007$.

Syöte

Lue seuraavat tiedot vakiosyötteestä.

• Syötteen ensimmäinen rivi sisältää luvut $N$ ja $K$ yhdellä välilyönnillä erotettuina.

Tuloste

Tulosta sellaisten mahdollisten tapojen lukumäärä asettaa kokonaisluvut lauseille, joilla Kukailta kuluu täsmälleen $K$ päivää lukemisen loppuun saattamiseen hänen lukiessaan optimaalisesti, modulo $1\,000\,000\,007$.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot.

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

Osatehtävät

Tehtävässä on 4 osatehtävää. Kunkin osatehtävän pistemäärä ja lisärajoitukset ovat seuraavat:

Osatehtävä 1 [4 pistettä]

• $N \le 10$.

Osatehtävä 2 [20 pistettä]

• $N \le 300$.

Osatehtävä 3 [25 pistettä]

• $N \le 3\,000$.

Osatehtävä 4 [51 pistettä]

Ei ole muita rajoituksia.

Esimerkit

Syöte 1

3 2

Tuloste 1

4

Huomautus

On 4 mahdollista tapaa asettaa kokonaisluvut lauseille niin, että häneltä kuluu 2 päivää lukemisen loppuun saattamiseen.

• Ensimmäisessä lauseessa on 1, seuraavassa lauseessa on 3 ja viimeisessä lauseessa on 2. Hän lukee kaksi ensimmäistä lausetta (numerot 1 ja 3) ensimmäisenä päivänä ja viimeisen lauseen (numero 2) toisena päivänä.
• Ensimmäisessä lauseessa on 2, seuraavassa lauseessa on 1 ja viimeisessä lauseessa on 3.
• Ensimmäisessä lauseessa on 2, seuraavassa lauseessa on 3 ja viimeisessä lauseessa on 1.
• Ensimmäisessä lauseessa on 3, seuraavassa lauseessa on 1 ja viimeisessä lauseessa on 2.

Syöte 2

10 5

Tuloste 2

1310354