Cuenta cuántos árboles binarios de búsqueda estructuralmente distintos guardan exactamente los valores \(1, 2, \dots, n\).

Entrada

Un entero \(n\) \((1 \le n \le 1000)\).

Salida

La cantidad, módulo \(10^9 + 7\).

Ejemplo 1

Entrada

3

Salida

5

Ejemplo 2

Entrada

1

Salida

1