大家知道cjc与mwy幸福的生活在了一起。第一天，他们生了1只猴子，第二天，他们又生了3只猴子。但是他们觉得这样生太慢了。 于是他们决定加大工作量，从第三天开始，他们每天生之前两天生的猴子的量的总和，现在问题来了，国家计划生育办找上门来决定给他们开罚款单，但是苦于实在数不清有多少只猴子，所以拜托聪明的你来告诉他答案。
第一行输入一个正整数t。接下来有t行，每行有一个正整数n（3<=n<=1000000000），代表计划生育办来查表的日期。
对于每个n，输出cjc与mwy总共生了多少只猴子，由于结果可能过大，因此要求输出总值取余1000000007的值。