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 x1 y x2 son expresiones correctas, (x1) − (x2) 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 (A) ((C)) (A)−(B) ((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))) (((B))) (A)−(A) (A)−(B) (B)−(A) (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 109.
Input
7 2 1 20 20 1 21 1 25 25
Output
6 20 0 212 307378150