Un giorno, JOI-kun ha ottenuto una macchina del tempo. Ha deciso di andare nel Giappone del IX secolo. Lì ha incontrato Kukai, uno dei monaci più famosi del Giappone dell'epoca. Il monaco voleva sviluppare un nuovo metodo di addestramento spirituale.

Il suo addestramento si svolge nel modo seguente:

• Kukai legge il sutra composto da $N$ frasi. Queste frasi sono ordinate, ed egli deve leggerle in ordine.
• Ogni frase ha un intero compreso tra $1$ e $N$, inclusi. Non ci sono due frasi diverse con lo stesso numero.
• Egli deve leggere la frase con l'intero $i$ ($1 \le i \le N$) nell'$i$-esimo periodo tra gli $N$ periodi di tempo uguali in cui è divisa una giornata. Ogni frase è così breve che per lui è sempre possibile leggere una frase in un periodo.

Kukai vuole leggere l'intero sutra il più velocemente possibile. Tuttavia, il numero di giorni necessari per finire dipende dagli interi associati alle frasi nel sutra. Kukai ha chiesto a JOI-kun di contare il numero di possibili assegnazioni degli interi alle frasi tali che a Kukai servano esattamente $K$ giorni per finire di leggere, se legge in modo ottimale.

Compito

Dato il numero di frasi $N$ e un intero $K$, calcola il numero di possibili assegnazioni degli interi alle frasi tali che a Kukai servano esattamente $K$ giorni per finire di leggere, se legge in modo ottimale, modulo $1\,000\,000\,007$.

Formato di input

Leggi i seguenti dati dallo standard input.

• La prima riga dell'input contiene $N$ e $K$, separati da un singolo spazio.

Formato di output

Stampa il numero di possibili assegnazioni degli interi alle frasi tali che a Kukai servano esattamente $K$ giorni per finire di leggere, se legge in modo ottimale, modulo $1\,000\,000\,007$.

Vincoli

Tutti i dati di input soddisfano le seguenti condizioni.

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

Sottoproblemi

Ci sono 4 sottoproblemi. Il punteggio e i vincoli aggiuntivi di ciascun sottoproblema sono i seguenti:

Sottoproblema 1 [4 punti]

• $N \le 10$.

Sottoproblema 2 [20 punti]

• $N \le 300$.

Sottoproblema 3 [25 punti]

• $N \le 3\,000$.

Sottoproblema 4 [51 punti]

Non ci sono vincoli aggiuntivi.

Esempi

Input 1

3 2

Output 1

4

Nota

Ci sono 4 possibili assegnazioni degli interi alle frasi tali che gli servano 2 giorni per finire di leggere.

• La prima frase ha 1, la frase successiva ha 3 e l'ultima frase ha 2. Egli legge le prime due frasi (numerate rispettivamente 1 e 3) il primo giorno, e l'ultima frase (numerata 2) il secondo giorno.
• La prima frase ha 2, la frase successiva ha 1 e l'ultima frase ha 3.
• La prima frase ha 2, la frase successiva ha 3 e l'ultima frase ha 1.
• La prima frase ha 3, la frase successiva ha 1 e l'ultima frase ha 2.

Input 2

10 5

Output 2

1310354