天花板人物 时间限制：1000ms 空间限制：256M 题目描述 某一天，校长花高价把毕业多年的小 Z 请回来，想见识一下这位能触及学校天花板的人物将会如何改变 校园。 现已知学校的天花板可近似看成 3 * n的长方形，小 Z 的粉刷工具每次可以粉刷 1 * 3 的区域，可以竖 着或者横着粉刷。由于材料有限，粉刷过的区域不会重复粉刷。请你帮校长算一下小 Z 最后粉刷出来的 天花板可能有几种不一样的方案。由于方案数可能很大，输出它模 10^9+7的余数即可。 注意：小 Z 在粉刷的时候必须完全刷满整个天花板，并且每一个小方格不能被重复刷 2 次

样例 #1

样例输入 #1

3

样例输出 #1

2

对于 100%的数据，1<=n<=200000

#include<bits/stdc++.h>
using namespace std;
int n;
const long long Mod=1000000007;
long long dg(int m){
    if(m<1) return 0; 
    else if(m==1||m==2||m==3) return 1;
         else if(m==3) return 2;
    return ((dg(m-1)+dg(m-3))%Mod);
}
int main()
{
	//freopen("pofhs.in","r",stdin);
	//freopen("pofhs.out","w",stdout);
	scanf("%d",&n);
	cout<<printf("%ll",dg(n));
	return 0;
}