Дизайн-проект

면접 대비

시간 제한2초메모리 제한1024 MB

요약

정수 한 변 길이를 갖는 정사각형 타일로 n×m 직사각형을 타일링하는 방법의 수를 10^9+7로 나눈 나머지를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 비트 연산, 구현
정답자: 아직 제출이 없습니다

문제

Ядан работает дизайнером. Она живет на одной из планет одной звезды.

В своих проектах Ядан любит замощать пол кафельными плитками. Для этого в ее распоряжении есть неограниченное число одинаковых плиток размером $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

예제 1
입력
```
2 2
```
예상 출력
```
2
```
예제 2
입력
```
3 3
```
예상 출력
```
6
```