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。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 206.196.186.173
※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1423856728.A.45E.html