问题 1296. -- 敬老师的手环Ⅱ

1296: 敬老师的手环Ⅱ

时间限制: 1 Sec  内存限制: 64 MB
提交: 12  解决: 3
[提交][状态][讨论版]

题目描述

敬老师是一位很喜欢手环的老师。话说敬老师即将去和barriery一起到北京实tong习ju,并且再过几天就是5.20,敬老师突发奇想,想要再DIY一个手环然后送给barriery。现在敬老师拥有的材料是一堆1*2的小矩形,每个小矩形都是一样的,他想要用这些小矩形拼出一个宽度为3周长为n的手环(手环靠近手的一侧和远离手的一侧是不同的)。于是他想要知道自己能拼出多少种不同的手环。

但是敬老师最近正在为实习做准备,没时间算这个,于是就把问题丢给了无所事事的wy。然而wy自己又只能看队友去实gao习ji,又要求这个题,于是就很郁闷,所以他把问题扔给了你。现在,你能帮wy解决这个问题吗?

输入

多组数据,数据组数不超过1000,请处理到文件结束。每组数据占一行,包含一个数(n <= 1e9)。

输出

每组数据输出一个数,即不相同的手环的种类数,要求答案对1e9+7取模。

样例输入

1
2
3
4

样例输出

0
6
0
11

提示

来源

[提交][状态][讨论版]