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 x1 i x2 són expressions correctes, (x1) − (x2) 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 (A) ((C)) (A)−(B) ((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))) (((B))) (A)−(A) (A)−(B) (B)−(A) (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 109.
Input
7 2 1 20 20 1 21 1 25 25
Output
6 20 0 212 307378150