2591: 薛定谔把妹法

薛定谔本体：

Acdaemon群的s&g、hjpyh、mmzl最近在研究薛定谔把妹法（以下简称xf）。

Xf中心思想是：事件在被观察以前，一直处在一个所谓“概率云”的状态下，一旦受到观察，则坍缩为实体。通俗一些，就是要给妹子神秘感。

Xf的理论(yy)依据是：这个谜一样的男子，这一刻薛定谔附体，带着量子论般深沉的哀愁，让她从此不能自拔。

Xf的经典实现如下：

每天给你那位心仪的女孩的抽屉里都放上精心准备的早餐，并且保持缄默不语，无论她如何询问，都不要说话。 如此坚持一至两个月，当妹子已经对你每天的准时早餐习以为常时，突然停止送餐，她心中一定会产生深深的疑惑及失落，同时会满怀兴趣与疑问找到你询问，这时 再一鼓作气将其拿下。

由于s&g、hjpyh、mmzl都没有女朋友并打算孤独一生，所以没有办法通过实验研究xf。于是他们找到了群里少数脱单的Eason®巨巨来帮忙研究，Eason®表示为了科学，这个没有问题。

Eason®决定对自己的妹子使用为期n天的xf，然而这并不顺利，Eason®妹子的IQ爆表，所以普通模式的xf对她是无效的。

满足下列任意一条即为普通模式的xf：

1、前n-1天送早餐，第n天不送早餐

2、前n-1天不送早餐，第n天送早餐

3、对于任意连续的3天，其中有偶数天（包括0天）没有送早餐

现在Eason®想知道对于一个给定的n天有多少种不同的xf对他的妹子无效

两个xf不同定义为两个xf的某一天送餐情况不相同

输入数据有多行，每行一个整数n（1<=n<=1000），表示给定n天

对于每组输入输出一个ans，ans=无效xf种数%（1e9+7）

1
2
3

2
3
4

Sample1的解释：

只有一天，不送早餐的话满足第一条“前n-1天送早餐，第n天不送早餐”，送早餐满足第二条“前n-1天不送早餐，第n天送早餐”