모자이크

한 건축가가 건물을 길고 가느다란 모자이크로 장식하려고 합니다. 모자이크는 세로 $N$인치, 가로 $M$인치인 직사각형 띠를 차지합니다. 이 띠를 한 변이 $1$인치인 정사각형 칸으로 이루어진 $N \times M$ 격자라고 생각합시다.

건축가에게는 두 종류의 타일이 있으며, 각 타일은 $2 \times 2$ 칸 영역 안에 들어갑니다.

• $2 \times 2$ 블록의 네 칸을 모두 덮는 정사각형 타일.
• $2 \times 2$ 블록에서 한 모서리 칸만 비우고 나머지 세 칸을 덮는 L자 타일(L-트로미노). 이 타일은 네 방향 중 어느 쪽으로든 회전할 수 있습니다.

건축가는 빈틈이나 겹침 없이 모든 칸을 정확히 한 번씩 덮어 띠 전체를 채우려고 합니다. 이때 서로 다른 무늬를 몇 가지나 만들 수 있는지 궁금해합니다.

두 모자이크는 같은 종류의 타일이 정확히 같은 위치에 놓였을 때에만 같다고 봅니다. 어떤 무늬를 회전하거나 뒤집어 타일의 위치가 달라지면 서로 다른 무늬로 셉니다. 예를 들어 아래의 네 $4 \times 16$ 모자이크는 서로 회전하거나 뒤집은 것이지만, 건축가는 이들을 네 개의 서로 다른 모자이크로 셉니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 한 줄에 두 정수 $N$과 $M$이 주어지며($2 \le N \le 10$, $2 \le M \le 500$), 각각 띠의 세로와 가로 길이(인치)입니다. 입력의 마지막 줄에는 두 개의 $0$이 주어지고, 이 줄은 테스트 케이스가 아닙니다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력합니다. $N \times M$ 띠를 타일로 채우는 서로 다른 방법의 수를 $10^6 = 1{,}000{,}000$으로 나눈 나머지입니다. 불필요한 공백이나 답 사이의 빈 줄은 출력하지 않습니다.