ProjectEuler 502 Counting Castles - 拼圖

502. Counting Castles

https://projecteuler.net/problem=502

我們定義一個石塊為一高度為1且寬度為正整數的長方形，並定義一個城堡為一堆石塊

堆疊起來的一種結構。

給定一高度為h且寬度為w的鉛直棋盤方格，我們可以依以下規則來構造城堡：

1. 石塊可以堆疊在其他石塊之上，但是不能突出下面石塊的邊界或架在多個石塊之上。

2. 所有石塊都和棋盤方格對齊。

3. 在同一高度的任兩石塊至少間隔一個空格。

4. 最下層必為一寬度為w的石塊。

5. 城堡最高點的高度恰為h。

6. 城堡必須由偶數個石塊組成。

下圖為w = 8、h = 5時的一個城堡的範例：

https://projecteuler.net/project/images/p502_castles.png

令F(w, h)為給定棋盤寬度w和高度h後，所有可構造出的城堡的數目。

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

請求出F(10^12, 100) + F(10000, 10000) + F(100, 10^12) mod 1000000007。

--