SUMMUL  Sum of products
One boy Petya decided to practice in addition and multiplication of numbers. For this he chose some positive integer n, and ordered all the ways to decompose it into two or more terms of positive integers, and the ways in different order terms are considered to be different (for example, for n = 3 there are three ways: 1 + 2, 2 + 1 and 1 + 1 + 1). Then he replaced all the plus signs with multiplication, and added the results (for n = 3: 1 × 2 + 2 × 1 + 1 × 1 × 1 = 5). After practicing for the day he decided to check the correctness of his calculations. Help Petya find the right answers.
Input
The first line contains T (1 <= T <= 1000)  the number of tests. Following T lines contain n (1 <= n <= 10 ^ 9).
Output
For each n from the input print the result Petya should get modulo 1000000007.
Example
Input: 3 1 2 3 Output: 0 1 5
hide comments
neeleshgoyal88:
20240420 12:41:23
my ans is coming correct for all the possible values i can calculate but still it is giving wrong answer :(


coder_619:
20200721 14:58:55
Read About Fibonacci Bisection Before Proceeding towards the problem 

candide:
20170429 23:27:30
Your first task: count the rabbits and find the formula ... 

Ouditchya Sinha:
20130527 07:10:34
Enjoyed solving this... :) 

numerix:
20101026 21:12:06
You can get your Python solution AC (even without psyco) if you implement the algorithm efficiently. 

pankaj:
20101024 18:13:22
python solution could not pass. c++ passed. :((( 
Added by:  Spooky 
Date:  20100309 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  Advancement Spring 2010, http://sevolymp.uuuq.com/, author: Alexey Shchepin 