问题 3861 --1.多米诺(Domino)

3861: 1.多米诺(Domino)

题目描述

  Alice最近在玩多米诺骨牌,她突发奇想,想用她的骨牌去铺一个2×n的长方形。Alice的骨牌是1×2的长方形木片,在铺骨牌的过程中她希望能满足如下要求:
1. 骨牌必须横向或竖向放置;
2. 骨牌不能超出2×n的长方形的边界;
3. 骨牌之间不能有重叠;
4. 骨牌需要将长方形铺满(即,铺2×n的长方形需要用n块骨牌)。
请问Alice有多少种方案,用1×2的骨牌铺满2×n的长方形?

例如,n=3时,铺2×3的长方形,骨牌的铺放方案有三种,如下图:

输入

输入一行,一个正整数n(n≥3),表示要铺满的长方形的大小为2×n。

输出

输出一个数,为满足上述要求的骨牌铺放方案数除以1,000,000,007的余数。

样例输入输出

输入#1 复制
3
输出#1 复制
3
输入#2 复制
4
输出#2 复制
5
输入#3 复制
9
输出#3 复制
55

提示

对于 40% 的数据,满足n≤10。
对于 70% 的数据,满足n≤100。
对于 100% 的数据,满足n≤1000。

序号 标题 作者 发表时间 费用 订购数 操作