레고 벽

레고 블록은 두 종류가 있다. 크기는 각각 1 × 1 × 1과 2 × 1 × 1이며, 순서대로 가로, 세로, 깊이이다. 두 종류 모두 무한히 쓸 수 있고, 같은 종류의 블록끼리는 구별되지 않는다.

블록은 항상 세워서 사용한다. 옆면은 같은 재료로 만들어져 있어서 크기 외에는 구별할 수 없다.

한 블록이 다른 블록 바로 위에 놓여 있으면 두 블록은 맞물려 있다고 한다. 블록 $b_0, b_1, \ldots, b_k$가 있고 모든 $1 \le i \le k$에 대해 $b_{i-1}$과 $b_i$가 맞물려 있으면, $b_0$과 $b_k$는 연결되어 있다고 한다. 배치 안의 모든 블록 쌍이 서로 연결되어 있으면 그 배치는 연결되어 있다고 한다.

폭 $w$, 높이 $h$, 깊이 1인 얇은 직사각형 벽을 만들려고 한다. 벽에는 구멍이 없어야 하고, 블록 배치는 연결되어 있어야 한다. 아래는 폭 4, 높이 3인 벽의 예이다.

아래 4 × 3 벽은 연결되어 있지 않으므로 조건을 만족하지 않는다.

구멍이 없고 연결된, 폭 $w$, 높이 $h$인 레고 벽을 만드는 방법의 수를 구하라. 수가 매우 클 수 있으므로 1000000007로 나눈 나머지를 구한다. 벽을 180도 회전한 것은 원래 벽과 같아 보이지 않는 한 다른 벽으로 본다.

한 줄에 공백으로 구분된 두 정수 $w$와 $h$가 주어진다. $w$는 벽의 폭, $h$는 벽의 높이이다.

$1 \le w \le 250\,000$, $2 \le h \le 250\,000$, $w \times h \le 500\,000$

구멍이 없고 연결된 $w \times h$ 레고 벽의 개수를 1000000007로 나눈 나머지를 한 줄에 출력한다.