题目502：数城堡

永恒的蓝色梦想

Project Euler 502 数城堡

题目：

我们把高度为 1 且宽度是整数的长方形称为一块。一个“城堡”就是一种堆叠的块的布局方式。

给定一个宽为 h 单位、高为 w 单位的游戏网格，依照下面的规则来生成一个城堡：

• 块可以放在其他块上，只要没有伸出来悬空的部分即可。
• 所有的块都严格按照网格对齐。
• 同一行上的任意的两个相邻的块之间至少有一个单位的空间。
• 最下面的一行必须是一个宽为 w 的完整的块。
• 城堡最高处的高度应正好等于 h。
• 城堡必须由偶数个块构成。
  

下图是一个 w 为 8、h 为 5 时的城堡样例：

                               
登录/注册后可看大图

定义 F(w,h) 为给定一个宽为 h 且高为 w 的网格时，所有有效的城堡的数量。

举个例子，F(4,2) 等于 10，F(13,10) 等于 3729050610636，F(10,13) 等于 37959702514，并且 F(100,100) 取模 1000000007 的结果为 841913936。

找出 F(10¹²,100)、F(10000,10000) 与 F(100,10¹²) 的和取模 1000000007 后的结果。