MOG Round #4Ended |
Durante un turno de clase Fito se estaba quedando dormido, y para despertarse un poco dibujó un tablero de N x M cuadraditos en una hoja de papel. Después en cada cuadradito trazó una de las dos diagonales posibles y coloreó una de sus dos partes completamente de negro. A continuación se muestra un ejemplo de un tablero de 2 x 4 que pudo haber hecho Fito antes y después de colorearlo.
Cuando terminó, se dio cuenta de que en su dibujo no habían dos triángulos del mismo color que compartieran un lado en común. Ahora Fito quiere saber de cuántas formas él puede dibujar un tablero de forma tal que cumpla con esta misma condición.
La entrada contiene dos números enteros N y M (1 <= N , M , <= 1000), la cantidad de filas y columnas respectivamente del tablero.
Se debe imprimir la cantidad de formas en las que se puede colorear un tablero de N x M de forma tal que no existan dos triángulos del mismo color que compartan un lado en común. Como la respuesta puede ser muy grande, imprima el resto que queda al dividir este valor por 1 000 000 007 (1e9 + 7)