Expresiones correctas P68813

En este problema consideramos las expresiones definidas de la manera siguiente:

• Toda variable es una expresión correcta;

• si $x$ es una expresión correcta, $(x)$ también lo es;

• si $x_1$ y $x_2$ son expresiones correctas, $(x_1) - (x_2)$ también lo es;

• nada más es una expresión correcta.

Por ejemplo, si el conjunto de variables es ${A, B, C}$, éstas serían algunas expresiones correctas:

$$A \qquad (A) \qquad ((C)) \qquad (A)-(B) \qquad ((A)-(B))-(A)$$

Haced un programa que, dados dos números $n$ y $m$, escriba el número de expresiones correctas de longitud exactamente $n$ que se pueden construir con $m$ variables.

Por ejemplo, para $n = 7$ y $m = 2$ el resultado debería ser 6, correspondiente a

$$(((A))) \qquad (((B))) \qquad (A)-(A) \qquad (A)-(B) \qquad (B)-(A) \qquad (B)-(B)$$

Entrada

La entrada consiste en diversos casos, cada uno con dos naturales $n$ y $m$ entre 1 y 25.

Salida

Para cada caso, escribid el número de expresiones correctas de longitud exactamente $n$ que se pueden construir con $m$ variables. Este número será siempre inferior a $10^9$.