Descripción

El Casique Guaso tiene un juego nuevo de cubos de Lego.

En el juego, hay n cubos de igual tamaño, donde el i-ésimo cubo viene en color ~i~. Usando estos cubos decide construir un muro.

Guaso construirá su muro sobre una base de Lego en forma de fila que tiene ~k~ lugares donde se pueden colocar los cubos.

Coloca los cubos de la siguiente manera:

• Primero, coloca el cubo de color ~1~ en un lugar arbitrario de la base.
• Para cada cubo de ~2~ a ~n~, lo coloca en un lugar vecino al cubo colocado anteriormente. Si ese lugar no está vacío, coloca el nuevo cubo encima de todos los demás.

Después de construir el muro, Guaso escribió en un trozo de papel una secuencia de longitud ~k~: en la posición i-ésima de la secuencia escribió el color del cubo superior en el lugar i-ésimo, o ~0~ si no hay ningún cubo en ese lugar.

Inmediatamente se preguntó cuántas secuencias diferentes podría haber escrito en el trozo de papel. Dos secuencias se consideran diferentes si existe una posición en la que difieren. Después de algún tiempo, ha conseguido calcular la solución, pero no está seguro de que sea correcta, así que te pide ayuda.

Entrada

En la única línea tiene los enteros ~n~ y ~k~ (~2 \le n,k \le 5000~), el número de cubos y la longitud de la base.

Salida

En la única línea, imprime la respuesta a la pregunta de Guaso, módulo ~10^9~ + ~7~

Subtareas

1- ~n, k \le 18~

2- ~n, k \le 50~

3- ~n, k \le 500~

4- ~n, k \le 5000~

Ejemplos

Entrada 1

4 3

Salida 1

8

Entrada 2

3 5

Salida 2

14

Entrada 3

100 200

Salida 3

410783331