Banta needs help

All submissions for this problem are available.
As we all know that Santa and Banta are good friends and they use to tease each other by giving mathematical questions to each other . So one day Santa has designed a problem for Banta . What Banta has to do is to count total number of chocolates , and the chocolate distribution is as follows ,
There are N students whom chocolate is to be distributed . Santa aligned each student in a line according to the marks in decreasing order and then start giving chocolates one by one to each student .
The first student will get f(1) number of chocolates .
The second student will get 2*f(2) number of chocolates .
The third student will get 3*f(3) number of chocolates .. and so on
so the Nth student will get n*f(n) number of chocolates .
f(x) is defined as
f(x) = 1 if x=1 or x =2
f(x) = f(x1) + f(x2) for all x > 2
As we all know that Banta is not very good at Maths so he needs your help , So help Banta by counting the total number of chocolates required . Since the answer can be very large print it Modulo 1000000007 .
.
Input
The first line of input contains T denoting the number of test cases. In every test case, Value of N will be given in a single line .
Output
For every test case print the total number of chocolates required in a new line.
Constraints
Should contain all the constraints on the input data that you may have. Format it like:
 1 ≤ T ≤ 10^5
 1 ≤ N ≤ 10^9
Subtasks
Subtask #1 (20 points), Time limit : 1 sec 1 ≤ T<=100000, N<=10^6
Subtask #2 (80 points), Time limit : 1 sec 1 ≤ T<=100000, N<=10^9
Example
Input: 3 1 2 4
Output: 1 3 21
Explanation
Testcase 1 : only 1 student is there and the total number of chocolates required is f(1) =1 . Testcase 2 : 2 students are there thus total number of chocolates required is 1* f(1) + 2*f(2) = 1*1 + 2*1 = 3 . Testcase 3 : 3 students are there thus total number of chocolates required is 1* f(1) + 2*f(2) + 3*f(3) = 1*1 + 2*1 + 3*2 + 4*3 = 21 .
Author:  abhi_1595 
Tags  abhi_1595 
Date Added:  13032017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions