Um dia, JOI-kun conseguiu uma máquina do tempo. Ele decidiu ir ao Japão do século IX. Lá, conheceu Kukai, um dos sacerdotes mais famosos do Japão naquela época. O sacerdote queria desenvolver uma nova forma de treinamento.

Seu treinamento é realizado da seguinte maneira:

• Kukai lê um sutra com $N$ frases. Essas frases têm uma ordem, e ele deve lê-las nessa ordem.
• Cada frase contém um número inteiro entre $1$ e $N$, inclusive. Duas frases diferentes nunca têm o mesmo número.
• Ele deve ler a frase com o número inteiro $i$ ($1 \le i \le N$) no $i$-ésimo dos $N$ períodos de igual duração em que o dia é dividido. Cada frase é tão curta que sempre é possível ler uma frase em um período.

Kukai quer ler o sutra inteiro o mais rápido possível. No entanto, o número de dias necessários para terminar depende dos números inteiros nas frases do sutra. Kukai pediu a JOI-kun que contasse o número de maneiras possíveis de atribuir números inteiros às frases para que Kukai leve exatamente $K$ dias para terminar a leitura, se ler de forma ótima.

Tarefa

Dados o número de frases $N$ e um número inteiro $K$, calcule o número de maneiras possíveis de atribuir números inteiros às frases para que Kukai leve exatamente $K$ dias para terminar a leitura, se ler de forma ótima, módulo $1\,000\,000\,007$.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha da entrada contém $N$ e $K$, separados por um único espaço.

Saída

Imprima o número de maneiras possíveis de atribuir números inteiros às frases para que Kukai leve exatamente $K$ dias para terminar a leitura, se ler de forma ótima, módulo $1\,000\,000\,007$.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

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

Subtarefas

Há 4 subtarefas. A pontuação e as restrições adicionais de cada subtarefa são as seguintes:

Subtarefa 1 [4 pontos]

• $N \le 10$.

Subtarefa 2 [20 pontos]

• $N \le 300$.

Subtarefa 3 [25 pontos]

• $N \le 3\,000$.

Subtarefa 4 [51 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

3 2

Saída 1

4

Explicação

Há 4 maneiras possíveis de atribuir números inteiros às frases para que ele leve 2 dias para terminar a leitura.

• A primeira frase tem o número 1, a seguinte tem o número 3 e a última tem o número 2. Ele lê as duas primeiras frases (numeradas 1 e 3, respectivamente) no primeiro dia e a última frase (numerada 2) no segundo dia.
• A primeira frase tem o número 2, a seguinte tem o número 1 e a última tem o número 3.
• A primeira frase tem o número 2, a seguinte tem o número 3 e a última tem o número 1.
• A primeira frase tem o número 3, a seguinte tem o número 1 e a última tem o número 2.

Entrada 2

10 5

Saída 2

1310354