28262번 - 초콜릿 비긴즈

코코는 화이트 초콜릿과 다크 초콜릿을 가지고 한별이와 틱택토 게임을 하고 있다. 틱택토의 규칙은 다음과 같다.

• $3\times 3$ 크기의 격자가 그려진 게임판을 준비한다.
• 두 플레이어가 번갈아 가면서 초콜릿을 게임판 위의 한 칸에 놓는다. 먼저 시작하는 플레이어는 화이트 초콜릿을, 상대 플레이어는 다크 초콜릿을 놓으며, 이미 초콜릿이 있는 칸에는 놓을 수 없다.
• 가로, 세로, 또는 대각선 방향으로 3개의 같은 색 초콜릿을 먼저 놓은 플레이어가 승리한다. 게임판이 가득 찰 때까지 아무도 승리하지 못했다면 두 플레이어는 비긴다.

코코는 매번 비기기만 하는 이 게임이 지겨워질 때쯤 하나의 궁금증이 생겼다. $N\times M$ 크기의 게임판에서 두 사람이 협력해서 비긴 게임을 만든다면, 그 결과로 나올 수 있는 서로 다른 게임판은 몇 가지일까? 코코의 궁금증을 해결해주자. 게임판의 크기가 달라져도 가로, 세로, 또는 대각선 방향으로 연속 3개를 놓으면 승리한다.

두 게임판은 같은 좌표에 서로 다른 초콜릿이 놓여 있는 곳이 하나라도 있다면 서로 다른 게임판이다. 최종적으로 초콜릿이 놓여 있는 위치가 모두 같으면, 초콜릿을 놓는 순서가 달라도 같은 게임판으로 본다. “대각선 방향”은 45도 각도의 오른쪽 아래 방향과 오른쪽 위 방향만을 의미한다.

정수 $N$과 $M$의 값이 첫 줄에 주어진다. ($1\le N,M\le 1000$)

$N\times M$ 크기의 게임판에서 틱택토 게임을 해서 나올 수 있는 서로 다른 비긴 게임판의 수를 $10^9+7$로 나눈 나머지를 출력한다.