题目描述

题目译自 European Girls' Olympiad in Informatics 2022 Day1 T2. Lego Wall

你手中有两种乐高积木，它们的尺寸分别是：$1 \times 1 \times 1$ 和 $2 \times 1 \times 1$（分别表示宽度、高度和深度，如下图所示）。这两种积木你有无限多块，每种积木之间没有区别，完全相同。

乐高积木必须竖直放置。积木侧面的材质完全一样，除了尺寸不同外，无法区分。

如果一块积木直接堆在另一块上面，我们就说这两块积木是锁在一起的。如果存在一串积木 $b_{0}, b_{1}, \ldots, b_{k}$，使得每对相邻的积木 $b_{i-1}$ 和 $b_{i}$（其中 $1 \leq i \leq k$）都锁在一起，那么我们就说积木 $b_{0}$ 和 $b_{k}$ 是连通的。如果一组积木中任意两块积木都是连通的，那么这组积木的排列就被认为是连通的。

现在，你想用这些积木搭建一堵宽度为 $w$、高度为 $h$、深度为 $1$ 的薄矩形墙。这堵墙不能有任何空洞，而且积木的排列必须是连通的。比如，下面是一个宽度为 $4$、高度为 $3$ 的乐高墙样例：

但下面这个 $4 \times 3$ 的乐高墙并不连通，所以不是我们想要的结果：

请你计算一下，有多少种方法可以搭建出这样的连通且无空洞的乐高墙？由于这个数字可能很大，请将结果对 $1000000007$ 取模输出。

注意，如果一个乐高墙旋转 180 度（镜像翻转）后看起来和原来不同，那么它会被视为一个不同的墙；除非翻转后和原来一模一样。

输入格式

输入只有一行，包含两个用空格分开的整数 $w$ 和 $h$ $(1 \leq w \leq 250000, 2 \leq h \leq 250000, w \times h \leq 500000)$，分别表示墙的宽度和高度。

输出格式

输出一个整数，表示尺寸为 $w \times h$ 的无空洞且连通的乐高墙的数量，对 $1000000007$ 取模。

2 2

3

对于 $2 \times 2$ 的墙，你可以搭建出以下三种连通的排列方式：

3 3

12

5 7

1436232

数据范围与提示

详细子任务附加限制及分值如下表所示。