Tenéis un suelo de dimensiones f × c, y una cantidad ilimitada de baldosas de tamaño 2 × 1. ¿De cuántas maneras podéis embaldosar el suelo?
Por ejemplo, hay 5 maneras de embaldosar un suelo 2 × 4:
(0,0)0.010a(0,0) (0,4)0.010b(0,4) (0,8)0.010c(0,8) (4,0)0.014a(4,0) (4,4)0.014b(4,4) (4,8)0.014c(4,8) (8,0)0.018a(8,0) (8,4)0.018b(8,4) (8,8)0.018c(8,8) (12,0)0.0112a(12,0) (12,4)0.0112b(12,4) (12,8)0.0112c(12,8) (16,0)0.0116a(16,0) (16,4)0.0116b(16,4) (16,8)0.0116c(16,8)
linewidth=2pt
-0a0c -0a16a -0c16c -16a16c -4a4c -8a8c -12a12c
(0,0)0.010a(0,0) (0,4)0.010b(0,4) (0,8)0.010c(0,8) (4,0)0.014a(4,0) (4,4)0.014b(4,4) (4,8)0.014c(4,8) (8,0)0.018a(8,0) (8,4)0.018b(8,4) (8,8)0.018c(8,8) (12,0)0.0112a(12,0) (12,4)0.0112b(12,4) (12,8)0.0112c(12,8) (16,0)0.0116a(16,0) (16,4)0.0116b(16,4) (16,8)0.0116c(16,8)
linewidth=2pt
-0a0c -0a16a -0c16c -16a16c -4a4c -8a8c -8b16b
(0,0)0.010a(0,0) (0,4)0.010b(0,4) (0,8)0.010c(0,8) (4,0)0.014a(4,0) (4,4)0.014b(4,4) (4,8)0.014c(4,8) (8,0)0.018a(8,0) (8,4)0.018b(8,4) (8,8)0.018c(8,8) (12,0)0.0112a(12,0) (12,4)0.0112b(12,4) (12,8)0.0112c(12,8) (16,0)0.0116a(16,0) (16,4)0.0116b(16,4) (16,8)0.0116c(16,8)
linewidth=2pt
-0a0c -0a16a -0c16c -16a16c -4a4c -4b12b -12a12c
(0,0)0.010a(0,0) (0,4)0.010b(0,4) (0,8)0.010c(0,8) (4,0)0.014a(4,0) (4,4)0.014b(4,4) (4,8)0.014c(4,8) (8,0)0.018a(8,0) (8,4)0.018b(8,4) (8,8)0.018c(8,8) (12,0)0.0112a(12,0) (12,4)0.0112b(12,4) (12,8)0.0112c(12,8) (16,0)0.0116a(16,0) (16,4)0.0116b(16,4) (16,8)0.0116c(16,8)
linewidth=2pt
-0a0c -0a16a -0c16c -16a16c -0b8b -8a8c -12a12c
(0,0)0.010a(0,0) (0,4)0.010b(0,4) (0,8)0.010c(0,8) (4,0)0.014a(4,0) (4,4)0.014b(4,4) (4,8)0.014c(4,8) (8,0)0.018a(8,0) (8,4)0.018b(8,4) (8,8)0.018c(8,8) (12,0)0.0112a(12,0) (12,4)0.0112b(12,4) (12,8)0.0112c(12,8) (16,0)0.0116a(16,0) (16,4)0.0116b(16,4) (16,8)0.0116c(16,8)
linewidth=2pt
-0a0c -0a16a -0c16c -16a16c -0b8b -8a8c -8b16b
Entrada
La entrada consiste en diversos casos, cada uno de los cuáles está formado por dos números f y c en una línea, con las dimensiones de un suelo. Podéis asumir que f está entre 1 y 3, que c ≥ 1, y que cada caso tendrá una solución menor a 109 (y que por tanto cabe en un entero).
Salida
Para cada caso de la entrada, tenéis que escribir una línea con el número de maneras de embaldosar el suelo.
Puntuación
Resolver casos de prueba como los del ejemplo 1, donde f = 1.
Resolver casos de prueba como los del ejemplo 2, donde f = 2.
Resolver casos de prueba como los del ejemplo 3, donde f = 3.
Resolver casos de prueba como los del ejemplo 4, donde f está entre 1 y 3.
Input
1 10 1 7
Output
1 0
Input
2 4 2 5
Output
5 8
Input
3 2 3 6
Output
3 41
Input
1 10 2 4 3 6
Output
1 5 41