Expressions correctes P68813

En aquest problema considerem les expressions definides de la manera següent:

• Tota variable és una expressió correcta;

• si $x$ és una expressió correcta, $(x)$ també ho és;

• si $x_1$ i $x_2$ són expressions correctes, $(x_1) - (x_2)$ també ho és;

• res més no és una expressió correcta.

Per exemple, si el conjunt de variables és ${A, B, C}$, algunes expressions correctes serien:

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

Feu un programa que, donats dos nombres $n$ i $m$, escrigui el nombre d’expressions correctes de longitut exactament $n$ que es poden construir amb $m$ variables.

Per exemple, per a $n =7$ i $m=2$ el resultat hauria de ser 6, que es correspon a

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

Entrada

L’entrada consisteix en diversos casos, cadascun amb dos naturals $n$ i $m$ entre $1$ i $25$.

Sortida

Per a cada cas, escriviu el nombre d’expressions correctes de longitut exactament $n$ que es poden construir amb $m$ variables. Aquest nombre sempre serà inferior a $10^9$.