|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Round #4Ended |
E - Tablero I
Languages: C, C++, Java, JavaScript, Pascal, Tiger, Haskell, Python, C#
Time & Memory limits: (details)
Dado un tablero de $N \times M$, se quiere conocer de cuántas maneras podemos cubrirlo completamente utilizando solamente fichas de dominó (rectángulos de $1 \times 2$ o $2 \times 1$) de forma tal que no se solapen entre ellas. Por supuesto, las fichas tampoco se pueden salir de los bordes del tablero.
Input
La entrada contiene dos números $N (1 \leq N \leq 12)$ y $M (1 \leq M \leq 100)$ que indican las dimensiones del tablero.
Output
Se debe imprimir la cantidad de formas en las que se puede cubrir el tablero con las características descritas anteriormente. Como la respuesta puede ser muy grande, imprima el resto que deja este valor al dividirlo por $1000000007 (10^9 + 7)$.
Sample test(s)
Input
1 2
Output
1
Input
2 2
Output
2
Input
2 3
Output
3