---

Problem 502

---

Counting Castles

We define a block to be a rectangle with a height of 1 and an integer-valued length. Let a castle be a configuration of stacked blocks.

Given a game grid that is w units wide and h units tall, a castle is generated according to the following rules:

1. Blocks can be placed on top of other blocks as long as nothing sticks out past the edges or hangs out over open space.
2. All blocks are aligned/snapped to the grid.
3. Any two neighboring blocks on the same row have at least one unit of space between them.
4. The bottom row is occupied by a block of length w.
5. The maximum achieved height of the entire castle is exactly h.
6. The castle is made from an even number of blocks.

The following is a sample castle for w=8 and h=5:

Let F(w,h) represent the number of valid castles, given grid parameters w and h.

For example, F(4,2) = 10, F(13,10) = 3729050610636, F(10,13) = 37959702514, and F(100,100) mod 1 000 000 007 = 841913936.

Find F(10¹²,100) + F(10000,10000) + F(100,10¹²) mod 1 000 000 007.

---

城堡计数

我们将高为1、长为整数值的长方形成为方块，而将一系列按特定方式堆叠在一起的方块称为城堡。

在一个宽度为w、高度为h的方阵上，按照如下方式构造城堡

1. 方块堆叠过程中不允许悬空或部分处于方阵之外。
2. 所有方块都与方阵对齐。
3. 在同一行的两个不同方块之间至少有一单位的间隔。
4. 最下方的一行必须包括一个长度为w的方块。
5. 最高高度恰好等于h。
6. 必须由偶数个方块构成。

如下是w=8且h=5时的一个城堡：

给定方阵的参数w和h，记所有有效的城堡数目为F(w,h)。

例如，F(4,2) = 10，F(13,10) = 3729050610636，F(10,13) = 37959702514，以及F(100,100) mod 1 000 000 007 = 841913936。

求F(10¹²,100) + F(10000,10000) + F(100,10¹²) mod 1 000 000 007。

---