HZNUOJ

生猴子系列3

Tags:
Time Limit:  1 s      Memory Limit:   32 MB
Submission:211     AC:12     Score:98.55

Description

大家知道cjcmwy幸福的生活在了一起。第一天,他们生了1只猴子,第二天,他们又生了3只猴子。但是他们觉得这样生太慢了。 于是他们决定加大工作量,从第三天开始,他们每天生之前两天生的猴子的量的总和,现在问题来了,国家计划生育办找上门来决定给他们开罚款单,但是苦于实在数不清有多少只猴子,所以拜托聪明的你来告诉他答案。

Input

第一行输入一个正整数t。接下来有t行,每行有一个正整数n3<=n<=1000000000),代表计划生育办来查表的日期。

Output

对于每个n,输出cjcmwy总共生了多少只猴子,由于结果可能过大,因此要求输出总值取余1000000007的值。

Samples

input
2 3 4
output
8 15

Author

LIN, Ouya