| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 2 | 2 | 2 | 100.000% |
Ядан работает дизайнером. Она живет на одной из планет одной звезды.
В своих проектах Ядан любит замощать пол кафельными плитками. Для этого в ее распоряжении есть неограниченное число одинаковых плиток размером 1ドル \times 1,ドル неограниченное число одинаковых плиток размером 2ドル \times 2,ドル и так далее, то есть в форме любого квадрата с целой стороной.
В этот раз ей предстоит разработать дизайн-проект замощения пола, имеющего форму прямоугольника размером $n \times m,ドル такими плитками. Ей стало интересно, сколько таких способов существует, и она попросила вас помочь ей с решением этой непростой задачи.
Посколько это число может быть очень большим, достаточно найти остаток от деления этого числа на 10ドル^9 + 7$.
Входной файл содержит два целых числа $n$ и $m$ (1ドル \le n \le 1000,ドル 1ドル \le m \le 6$) --- размеры прямоугольника, форму которого имеет пол.
В выходной файл выведите единственное число --- количество способов замостить прямоугольник квадратами, взятое по модулю 10ドル^9 + 7$.
2 2
2
3 3
6